Các thuật ngữ cơ bản khi tự học lập trình web

Nếu bạn mới bắt đầu học lập trình web, bạn sẽ cảm thấy khá lúng túng trước khá nhiều thuật ngữ mới trong lĩnh vực này. Tài liệu này sẽ giúp bạn làm quen với một số khái niệm lập trình web cơ bản, khởi đầu cho quá trình tự học lập trình web của bạn sau này được dễ dàng hơn.

WWW – World Wide Web

World Wide Web (WWW, thường được gọi tắt là Web) là một trong những dịch vụ được dùng rất phổ biến trên Internet. Được xây dựng chủ yếu trên nền văn bản, đồ họa và các hiệu ứng tương tác, Web càng được sử dụng phổ biến và giờ đây đã là một phần quen thuộc của cuộc sống. Tuy nhiên, để tạo được các trang web “động”, có tương tác với người dùng, thông tin được cập nhật thường xuyên, có kiểm tra dữ liệu nhập, có hiệu ứng chuyển động, … bạn phải lập trình cho các trang web. Lập trình web sẽ giúp cho các trang Web của bạn cuốn hút người dùng hơn, tạo ấn tượng với người xem hơn nhờ bạn có thể chủ động lập trình “điều khiển” các nội dung của trang Web theo ý mình.

HTTP – HyperText Transfer Protocol

HTTP, giao thức chuyển giao siêu văn bản trên Web, được xem như là một ngôn ngữ “nói chuyện” giữa Web clients và Web servers. Giao thức này là tập hợp các qui định dùng để trao đổi các tài liệu (văn bản, hình ảnh, âm thanh, video, các tập tin đa truyền thông,…) giữa Web server và trình duyệt Web. Người ta gọi giao thức HTTP là giao thức phi trạng thái (stateless) bởi mỗi lệnh đều được thực thi một cách độc lập, lệnh sau không biết gì về lệnh trước đó.

Kết quả hình ảnh cho link web

URL – Uniform Resource Locator

Khái niệm này ra đời cùng lúc với Internet, vấn đề đặt ra lúc đó là cách thức qui định đặt tên địa chỉ như thế nào nhằm mục đích để giúp cho người dùng dễ dàng truy cập đến nguồn tài nguyên trên Web. Vậy URL là gì?, đó chính là một địa chỉ trên Internet, cú pháp đầy đủ của URL có dạng : scheme://<host> [:port] [<path> [?<querystring>]] Trong đó:

  • scheme: lọai dịch vụ Internet, với dịch vụ thông dụng nhất là http dùng để truy cập tài nguyên tại các Web server;
  • host: địa chỉ máy chủ chứa tài nguyên (ví dụ www.w3schools.com, www.vnexpress.net,…);
  • port: cổng dịch vụ trên máy chủ, giá trị này có thể bỏ trống và có giá trị là 80 nếu lọai dịch vụ là http;
  • path: đường dẫn và tên của tập tin tài nguyên trên máy chủ;
  • querystring: các tham số được gửi kèm theo http để cung cấp thêm thông tin, phục vụ cho xử lý nào đó tại Web server.                                                                                                                                                         Đối với các trang web tĩnh, là các trang web nội dung thường ít được cập nhật sửa đổi, tham số querystring  thường không thấy.

Ví dụ: http://www.legend.net.uk/resources/gloss.html http://www.tuoitre.com.vn/Tianyon/Index.aspx?ArticleID=238657&ChannelID=3

HTML – HyperText Markup Language

Khi bạn sử dụng trình duyệt (Web browser) để duyệt trang Web nào đó bạn sẽ thấy trong trang Web luôn có các liên kết siêu văn bản – HyperText (một từ, một câu, một hình ảnh,… trong trang Web) mà khi click vào sẽ đưa bạn đến trang Web khác). Những liên kết kết siêu văn bản chính là đặc trưng của WWW nên các trang Web thường được gọi là các tài liệu siêu văn bản. Để xây dựng các tài liệu này, bạn sẽ sử dụng ngôn ngữ HTML (HyperText Markup Language – Ngôn ngữ đánh dấu siêu văn bản) là ngôn ngữ quy định cách định dạng văn bản để đưa lên Web cùng với sự xác định các mối liên kết siêu văn bản. Như vậy, trang web (trang HTML) là tập hợp gồm những dòng văn bản và các thẻ đánh dấu (Tag) theo cấu trúc và trình tự xác định. Các thẻ HTML này sẽ quy định cách hiển thị văn bản, hình ảnh…. trên trình duyệt để các trình duyệt Web có thể hiểu và hiển thị thông tin theo ý bạn. CSS – Cascading Style Sheets

Style Sheet là gì?

Là một tập hợp các qui định về cú pháp khai báo dùng để định dạng trang web, chính xác hơn là nơi dùng để định nghĩa các style. Giả sử, trong một trang web, bạn muốn tất cả các tag <h1> có chữ màu đỏ, thông thường bạn sẽ sử dụng thuộc tính style và khai báo cho từng tag <h1>. Nhưng đối với Style Sheet thì bạn sẽ khai báo một lần và áp dụng cho toàn bộ trang web hoặc cho cả website. Nói đơn giản hơn, Style Sheet giống như là một quy tắc dùng để “trang trí” trang web.

Cascading Style Sheets

CSS là một chuẩn của Internet do W3C định nghĩa và chính thức giới thiệu vào tháng 12/1996. Sở dĩ gọi nó là Cascading (xếp tầng) là vì hiệu ứng của style có thể được kế thừa từ các tag khác, nếu style được định nghĩa trong một tag cha thì các tag con (nằm trong tag cha) sẽ kế thừa style đó. Ví dụ: 3 dòng văn bản sau đều có màu đỏ, vì kế thừa style của tag <p>

<p style=”color:red”>

<b>Trung Tâm Tin Học</b> <br>

Đại Học Khoa Học Tự Nhiên TP.HCM<br>

<font size=”+4″><i>Thông báo chiêu sinh khóa 155</i></font>

Ngôn ngữ lập trình JavaScript 

JavaScript là ngôn ngữ kịch bản (scripting language) dùng để tương tác với các trang HTML dựa trên đối tượng (object-based scripting language ). Các chương trình JavaScript thường được nhúng (embedded) trực tiếp vào tập tin HTML bằng tag <script> hoặc tích hợp (integrated) vào trang web thông qua một tập tin được khai báo trong tag <link>.

JavaScript có một số đặc điểm sau:

  • Là một ngôn ngữ thông dịch(interpreted language), nghĩa là các script thi hành không cần biên dịch trước (precompile). Trình duyệt dịch script, phân tích và thi hành ngay tức thời.
  • Lập trình theo cấu trúc (Structured progarming)
  • Giống như C và Java, có phân biệt chữ HOA và thường Hiện nay đa số các trình duyệt đều hỗ trợ JavaScript nên các trang web có Javascript có thể chạy trên bất kỳ trình duyệt nào. Để học JavaScript một cách hiệu quả, bạn nên áp dụng phương pháp “học qua ví dụ” (Learning By Example), đương nhiên là bạn phải có nền tảng căn bản trước đó. Hiện nay trên internet bạn có thể tìm thấy vô số các đoạn JavaScript từ đơn giản đến phức tạp, bạn có thể lấy về dùng mà không cần phải tìm hiểu chi tiết tường tận, chỉ cần biết cách khai báo sử dụng trong trang HTML của mình là có thể quan sát để hiểu ý nghĩa của đoạn code đó.

Lập trình front-end

Lập trình viên Front – End là người xây dựng các chức năng giao tiếp, tương tác trực tiếp với người dùng. Khi bạn duyệt các trang web, từ font chữ, màu sắc cho tới các menu chọn và các thanh trượt, các hình ảnh chuyển động quảng cáo, các hiệu ứng chuyển màu hay di chuyển văn bản, hình ành… đều là tác phẩm của Lập trình viên Front – End. Các Lập trình viên Front-end sẽ chịu trách nhiệm thể hiện giao diện của trang web theo đúng yêu cầu thiết kế , những tương tác, chuyển động theo đúng ý tưởng sáng tạo sao cho mang lại cho người dùng những trải nghiệm giao diện ấn tượng, bắt mắt và phong cách nhất.

Front-end cơ bản

Lập trình front-end ở mức cơ bản chỉ cần thông thạo HTML, CSS, và JavaScript để làm chủ giao diện người dùng với font chữ, màu sắc, thanh trượt, thực đơn, hình ảnh, hiệu ứng tương tác,…

Kết quả hình ảnh cho front-end cơ bản

Front-end nâng cao 

Ngoài các kiến thức cơ bản, các lập trình viên front-end cần phải làm quen với các framework như Bootstrap để đảm bảo nội dung có thể hiển thị tốt trên mọi thiết bị khác nhau, các trình duyệt khác nhau và AngularJS để cải thiện tốc độ tương tác cũng như bổ sung các hiệu ứng chuyển động đẹp mắt, ấn tượng vào ứng dụng web một cách nhanh chóng hơn.

Kết quả hình ảnh cho Front-end nâng cao

Lập trình back-end

Lập trình web không chỉ có những cần giao diện ở front-end mà cần những dữ liệu, xử lý ở mức server. Hay nói cách khác, để có được những gì thể hiện trên website ở front-end phải có các dữ liệu, thông tin từ các chức năng do lập trình web back-end cung cấp. Từ “hậu trường”, lập trình viên back-end sẽ xây dựng và thực hiện các giải thuật để tính toán, truy cập và xử lý dữ liệu để cung cấp chính xác, nhanh chóng theo các yêu cầu nhận được.

Có rất nhiều ngôn ngữ để lập trình back end như: PHP, ASP.NET, Java, Python,… cho phép bạn viết các đọan mã lệnh (source code) mà sẽ được biên dịch và thi hành tại Web server, sau đó trả kết quả về client dưới dạng HTML, CSS và JavaScript. Với lập trình back-end, bạn có thể lập trình, xây dựng các trang web động, có tương tác với cơ sở dữ liệu và kết nối với các dịch vụ Web Service phục phục vụ đa dạng yêu cầu của người dùng trong thực tế.

Hiện nay, các thông tin tuyển dụng Lập trình viên back-end khá cao và thường yêu cầu ứng viên có thêm kiến thức, kinh nghiệm liên quan đến các framework MVC, có kiến thức về web server và các phần mềm quản lý phiên bản như Git/SVN.

Lập trình Full-stack

Nhưng để có được ứng dụng hoàn chỉnh, nếu chỉ có lập trình viết mã lệnh không thì chưa đủ. Bạn sẽ cần có cơ sở dữ liệu để lưu thông tin của ứng dụng, bạn cần có web server, hệ điều hành để có thể deploy ứng dụng mà từ đó người dùng có thể khai thác được. Tập hợp tất cả các phần mềm, công nghệ này tạo thành solution stack, hệ thống nền tảng để ứng dụng có thể hoạt động được.

Một số solution stack thông dụng

 

Kết quả hình ảnh cho LAMP-Stack

LAMP-Stack, được dùng khá phổ biến, hầu hết các website đều sử dụng stack này và các hosting cho PHP cũng đang dùng stack này.

Kết quả hình ảnh cho Một số solution stack thông dụng

WAMP-Stack tương tự như LAMP Stack nhưng khác ở hệ điều hành Windows. WAMP Stack được dùng trong học tập, nghiên cứu nhiều hơn do đã quá quen thuộc với hệ điều hành Windows.

Hình ảnh có liên quan

WINS – Stack này bao gồm các công nghệ của Microsoft. Trong đó Windows là hệ điều hành, web server là Internet Information Services c, .NET là môi trường phát triển ứng dụng khá phổ biến với ngôn ngữ lập trình hướng đối tượng C# và SQL Server là hệ quản trị cơ sở dữ liệu quan hệ. Đây là lựa chọn cho các giải pháp mang tính thống nhất vì việc phối hợp giữa các thành phần sẽ dễ dàng hơn và mang tính bảo mật khá ổn định hơn. Nếu bạn chọn mình trở thành Lập trình viên Full-stack, ngoài kiến thức lập trình back-end, bạn cần có kiến thức IT tổng quát và khả năng tìm hiểu sâu khi cần thiết bất kỳ vấn đề gì về hệ điều hành, Web Server, cơ sở dữ liệu, web framework. Bạn có thể tham khảo các giải pháp hiện nay đang áp dụng tại các doanh nghiệp tại Việt Nam để chọn cho mình hướng đi phù hợp.

Kết quả hình ảnh cho khach san new world Full-stack

Kết quả hình ảnh cho zing Full-stack

Chuyên gia thuật toán vô địch Facebook Hacker Cup giờ ra sao?

Facebook Hacker Cup là một kỳ thi Thuật Toán rất nổi tiếng của Facebook, và mỗi năm số người người tham dự ngày một đông. Một số người cho rằng, tham dự những kỳ “thi thố” để làm gì? Thật ra những người trong giới thuật toán tham dự các kỳ thi, nó không đơn thuần mang ý nghĩa “thi thố” hay “thể hiện” mà nó còn là dịp để các họ rèn giũa lại kiến thức của mình. Luyện “não” cũng giống như tập “gym” vậy, bạn luyện đều đặn và đúng cách “não” sẽ khỏe mạnh và làm việc được lâu dài. Ngược lại nếu bạn bỏ bê chúng, một ngày nào đó não sẽ có “bụng bia”
Nhà thơ Vũ Đình Liên trong bài thơ “Ông Đồ” đã từng thốt lên “Những người muôn năm cũ Hồn ở đâu bây giờ?” Khi ông không còn thấy những ông Đồ xuất hiện trong dịp lễ để cho các câu đối hay chơi chữ nữa. Vậy thì bạn có bao giờ tự hỏi rằng những người đạt giải kỳ thi này họ “ở đâu bây giờ?”.
Hãy cùng Big-O Coding tìm hiểu xem những nhà vô địch Facebook Hacker Cup ngày xưa hiện giờ họ ở đâu? làm gì? và công việc của họ như thế nào? nhé.

Petr Mitrichev

Anh là một lập trình viên người Nga, vô địch Facebook Hacker Cup vào các năm 2011, 2013 và 2017. Ngoài ra anh đã đạt rất nhiều thành tích ở những cuộc thi khác như Huy chương vàng IOI (2000, 2002) , huy chương vàng ACM ICPC World Final (2003, 2005), vô địch Google Code Jam(2006) và Topcoder Open (2006, 2013, 2015),… Hiện tại anh đang làm cho Google với vị trí kỹ sư về Google Search.

Tiancheng Lou

Anh là một lập trình viên người Trung Quốc, đoạt giải 3 Facebook Hacker Cup vào năm 2011 và 2012. Anh còn đạt những thành tích khác như vô địch Google Code Jam vào năm 2008 và 2009, đạt thứ hạng cao trên Topcoder và Codechef,.. Anh hiện đang là Software Engineer cho Google.

Khúc Anh Tuấn

Anh là một lập trình viên người Việt Nam,từng du học tại Đại học công nghệ Nayang Singapore, anh đã xuất sắc vượt qua các lập trình viên lừng danh toàn cầu giành vị trí thứ nhì Facebook Hacker Cup năm 2011. Anh hiện đang là Software Engineer cho Uber.

Tomek Czajka

Là một lập trình viên người Mỹ, anh tốt nghiệp ở đại học Purdue với tấm bằng Master of Science năm 2007. Anh đạt nhiều thành tích cao trong các kì thi về lập trình, phải kể đến như hạng nhì cuộc thi Facebook hacker cup năm 2012 và 2014, giải nhất cuộc thi TopCoder Open năm 2008, hạng 5 cuộc thì Google Code Jam năm 2003 và 2004 . Anh hiện đang làm việc tại Tập đoàn Công nghệ Khai phá Không gian (Space Exploration Technologies Corp) viết tắt là SpaceX với vị trí kỹ sư phần mềm. Trước đó anh từng làm việc cho Google (2007 – 2013).

Jakub Pachocki

Anh tốt nghiệp Cử nhân Khoa học máy tinh ở đại học Warsaw (Ba Lan) năm 2013, sau đó anh lấy được tấm bằng Tiên Sĩ về Khoa học máy tinh năm 2016 tại đại học Carnegie Mellon với bài báo “Graphs and Beyond: Faster Algorithms for High Dimensional Convex Optimization”. Anh đã đạt giải nhì tại cuộc thi Facebook Hacker Cup năm 2012, anh đã từng 2 lần thực tập cho Facebook (2011,2012). Năm 2016 – 2017 ,anh làm việc tại đại học Harvard. Hiện tại anh đang nghiên cứu viên về lĩnh vực trí tuệ nhân tạo tại OpenAI (San Francisco)

Gennady Korotkevich

Còn được biết đến với biệt danh “tourist”, anh hiện đang học ở đại học tổng hợp ITMO ở Nga. Korotkevich tham gia nhiều cuộc thi và đã đạt được rất nhiều thành tích, như vô địch Facebook Hacker Cup năm 2014 và 2015, vô địch TopCoder Open năm 2014, vô địch Google Code Jam trong 4 năm liên tiếp (2014 – 2017), vô địch ACM-ICPC World Finals năm 2013 và 2015.

Dmytro Soboliev

Anh là người Ukraine, anh tốt nghiệp thạc sĩ về lĩnh vực toán học ứng dụng ở Viện Bách khoa Kiev. Anh đã xuất sắc giành được Giải nhì Facebook Hacker Cup 2015. Anh từng là Junior C++ Developer ở công ty Luxsoft (2012 – 2014). Hiện anh đang làm ở Amazone Web Services với ví trí Software Development Engineer.

Gleb Evstropov

Anh tốt nghiệp khoa Khoa học máy tinh và điểu khiển học tại Đại học Tổng hợp Quốc gia Moskva , anh đạt nhiều thành tích cao trong các cuộc thi lập trình như Huy chương vàng tại ACM ICPC World Finals 2014 và 2015, giải ba cuộc thi Facebook Hacker Cup 2015, huy chương vàng IOI 2010. Hiện anh đang là giảng viên tại trường đại học nghiên cứu quốc gia ở Moskva, Nga.

Tiếng Anh chuyên ngành Công nghệ thông tin

Computer science: Khoa học máy tính

 

Graphs (Đồ thị)

 

Directed Graphs

Undirected Graphs

Shortest Paths

Spanning Trees: Cây khung

Một số lưu ý khi viết bài trên YeuLapTrinh

1 – Sử dụng Latex

Website có hỗ trợ công cụ viết công thức toán học Latex. Mình xin được giới hiệu cách sử dụng ở dưới đây

  • Bài viết nào dùng đến Latex thì bắt buộc phải thêm một dòng ở trên cùng
    • Viết cùng trên một dòng thì dùng: $...$
    • Viết công thức trên cả một dòng thì dùng: $$...$$

Thí dụ:

[mathjax]

Bài viết này sử dụng Latex. Test...

$a^2 + b_i^3 \ge c_{i+1}^5 + d_{x+1}^{y+1}$

2 – Tránh lỗi khi chèn code

Hầu hết các bài viết các bạn đều chèn code vào, nhưng nhiều bạn chèn code vẫn chưa đúng cách, gây lỗi. Nên mình xin được hướng dẫn cách chèn code và chú ý khi chèn code để không bị lỗi.

viet-bai-yeulaptrinh

Tab “Trực quan” và Tab “Văn bản”

Khi soạn thảo, bạn có 2 tab là “Trực quan”” và “Văn bản”.

  • Tab “Trực quan” là soạn thảo văn bản tương tự như Word
  • Tab “Văn bản” là chỉnh sửa văn bản dạng HTML. Đây là tab mà bạn chèn code

Lỗi khi soạn thảo các bạn cần chú ý ở đây là:

  • Không viết chèn code ở tab “Trực quan”, phải chèn ở trong Tab “Văn bản”
    • Bươc 1: Mở tab “Văn bản”
    • Bước 2: Chèn đoạn HTML với mẫu: <pre lang=”ten_ngon_ngu_lap_trinh”>Viết code ở đây</pre>
      • ten_ngon_ngu_lap_trinh là c, cpp, python, php, java, … Xem thêm ở GeSHi

Vd:

<pre lang="cpp">
int a, b;
int c,d;
  • Chú ý 2: Sau khi chèn code, việc chuyển đổi giữa 2 tab “Trực quan” và “Văn bản” sẽ gây lỗi. Ví dụ:
    • < thành &lt;
    • > thành &gt;
  • Vì vậy nên soạn thảo trên tab “Trực quan” xong xuôi thì mới chuyển sang tab “Văn bản” để chèn code. Tránh hành động chuyển đổi giữa 2 tab sẽ gây lỗi cho code.

 

 

 

 

 

MULONE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';//MULONE.INP';
  fo = '';//MULONE.OUT';
  maxn = 10000000;
var
  n,test,t : longint;
  kq : array[1..maxn] of longint;
 
procedure sol;
var
  i,nho,tong : longint;
  count : longint;
begin
  tong:=0; nho:=0; count:=0;
  for i:=1 to n do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=n-1 downto 1 do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=count downto 1 do write(kq[i]);
  writeln;
end;
 
BEGIN
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
  readln(T);
  for test:=1 to T do
    begin
      readln(N);
      sol;
    end;
  close(input);
  close(output);
END.

C11PNUM – spoj

Đề bài:

Thuật toán:

  • Sàng nguyên tố
  • Tính các tích k số nguyên tố liên tiếp để cập nhập cho kết quả

Code:

const   fi='';
        fo='';
        oo=3000000;
var     k,t,i,j,tt:longint;
        tam,n,res:qword;
        f:text;
        tmp:array[2..oo] of boolean;
        ngto:array[1..oo] of longint;
        d	:longint;
function max(a,b:qword):qword;
begin
        if a>b then exit(a) else exit(b);
end;
procedure xl;
var     i,j :longint;
begin
	for i:=1 to d-k+1 do
		begin
			tam :=1;
			for j:=i to i+k-1 do
			begin
				tam := tam*ngto[j];
			end;
                        if tam>n then break else res := max(res,tam);
		end;
end;
procedure init;
begin
        for i:=2 to trunc(sqrt(oo)) do
                if tmp[i]=false then
                        begin
                            j:=i*i;
                            while j<=oo do
                                begin
                                    tmp[j]:=true;
                                    j:=j+i;
                                end;
                        end;
        d:=0;
        for i:=2 to oo do
                if tmp[i]=false then begin inc(d); ngto[d]:=i; end;
        j:=d;
end;
procedure nhap;
begin
    assign(f,fi);reset(f);
    assign(output,fo);rewrite(output);
    read(f,t);
    for tt:=1 to t do
        begin
            read(f,n,k);
            res := 0;
            xl;
            if res=0 then writeln(-1) else writeln(res);
        end;
    close(f);close(output);
end;
begin
    init;
    nhap;
end.

Ứng dụng của đồ thị

Ta đang sống trong một thế giới mà mọi vật được liên kết, các thành phố được liên kết với nhau bởi các con đường, con người liên kết với nhau trên mạng xã hội… những liên kết như vậy chính là hình hài của đồ thị. Một trong những đồ thị lớn mà ai trong chúng ta cũng biết đó chính là Internet hay là mạng tìm kiếm Google.

Đồ thị được sinh ra từ nhu cầu giải quyết những vấn đề thực tế của đời sống. Ví dụ như là bài toán ‘7 cây cầu Königsberg’ từ những năm 1720. Đồ thị là một phần quan trọng trong Toán học rời rạc, là cơ sở của Tin học. Ứng dụng của nó vô cùng rộng, áp dụng vào trong nhiều lĩnh vực. Trong phạm vi bài viết, tác giải chỉ đề cập đến một vài ứng dụng thực tế cơ bản.

Bài toán bảy cây cầu

Tìm đường đi ngắn nhất

Trong thực tế, ta luôn phải lựa chọn đường đi ngắn nhất để đi sao cho tiết kiệm xăng. Đầu tiên là biểu diễn mạng giao thông dưới dạng đồ thị rồi sử dụng thuật toán tìm đường đi ngắn nhất. Thường thì mọi người sử dụng thuật toán Dijkstra nhưng giả dụ với dữ liệu không lồ như của Google Map thì thuật toán này không thể đáp ứng. Google đang sử dụng một thuật toán có tộc độ nhanh hơn nhiều thuật toán Dijkstra.

Tìm đường trên Google Maps

Nhưng nếu muốn tìm đường giữa Hà Nội và New York thì sao? Giữa chúng có hàng tỉ tỉ giao lộ thì phải làm thế nào?

 

Tô màu đồ thị

Ứng dụng điển hình của tô màu đồ thị là bài toán tô màu bản đồ. Làm sao để tô màu bản đồ sao cho không có hai vùng kề nhau có cùng màu và số màu cần dùng là ít nhất.

Biểu diễn bài toán dưới dạng đồ thị:

  • Coi mỗi vùng là một đỉnh
  • Hai đỉnh có cạnh nối với nếu hai vùng tương ứng kề nhau

Bài toán trở thành tô màu các đỉnh của đồ thị, giải quyết sẽ đơn giản hơn bài toán ban đầu.

Bài toán tô màu bản đồ

Một ứng dụng khác là trong bài toán xếp lịch ở UET, làm sao để xếp lịch thi cho sinh viên sao cho nếu sinh viên học môn A và môn B thì hai môn này không thi cũng lúc, ngoài ra kì thi cần kết thúc sớm nhất.

Với bài này ta giải quyết thế nào?

Gọi mỗi môn học là một đỉnh, hai đỉnh được nỗi với nhau nếu tồn tại học sinh học cả 2 môn này. Bài toán giờ trở thành bài toán tô màu cho các đỉnh.

 

Đồ thị hai phía

graph-yeulaptrinh.pw

Đồ thị ghép cặp hẹn hò

Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp, quan hệ hôn nhân giữa tập những người đàn ông và tập những người phụ nữ, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v…