Lý thuyết đồ thị - Đường đi - Chu trình - Đồ thị liên thông

Lý thuyết đồ thị - Đường đi - Chu trình - Đồ thị liên thông

Đồ thị: là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị thông qua kiểu và số lượng cạnh nối giữa các cặp đỉnh của đồ thị.

Dưới đây là một ví dụ về mạng máy tính bao gồm: mỗi máy tính là một đỉnh, mỗi kênh điện thoại kết nối là cạnh của đồ thị

Đồ thị: Mạng máy tính

Đồ thị: Mạng máy tính

Trong mạng máy tính trên, mỗi máy tính là một đỉnh của đồ thị, các kênh điện thoại là cạnh của đồ thị, không có hai cặp cạnh nào nối cùng một cặp đỉnh. Ta gọi đây là đơn đồ thị vô hướng.

Đơn đồ thị vô hướng: Đơn đồ thị vô hướng G = <V,E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.

Trong trường hợp giữa máy tính nào đó thường xuyên phải truyền tải thông tin nên người ta xây dựng thêm một kênh điện thoại nữa để tăng khả năng truyền tải thông tin, khi đó hai máy tính sẽ có nhiều hơn một kênh điện thoại kết nối. Ta gọi đây là đa đồ thị vô hướng.

Mạng máy tính đa kênh thoại

Mạng máy tính đa kênh thoại

Đa đồ thị vô hướng: G = <V, E> bao gồm V là tập các đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. e1, e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Mạng máy tính đa kênh thoại có khuyên

Mạng máy tính đa kênh thoại có khuyên

Giả đồ thị vô hướng: G = <V, E> bao gồm V là tập đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử (hai phần tử không nhất thiết phải khác nhau) trong V được gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e =(u, u), trong đó u là đỉnh nào đó thuộc V.

Trong nhiều mạng, các kênh kết nối giữa hai máy tính chỉ có thể truyền tải thông tin theo một chiều.Chẳng hạn máy tính đặt tại Hà Nội có thể truy cập dữ liệu của máy tính đặt tại Hải Phòng, nhưng máy tính ở Hải Phòng không thể truy cập dữ liệu của máy tính ở Hà Nội. Để mô tả mạng máy tính này chúng ta dùng khái niệm đồ thị có hướng.

Mạng máy tính có hướng

Mạng máy tính có hướng

Đơn đồ thị có hướng G = <V, E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung.

Trong trường hợp có nhiều hơn một kênh có hướng kết nối giữa hai đỉnh của đồ thị, để mô tả mạng máy tính này ta dùng khái niệm đa đồ thị có hướng.

Mạng máy tính đa kênh một chiều

Mạng máy tính đa kênh một chiều

Đa đồ thị có hướng G = <V, E> bao gồm V là tập đỉnh, E là cặp có thứ tự gồm hai phần tử của V được gọi là các cung. Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.

Loại đồ thị Cạnh Có cạnh bội Có khuyên
Đơn đồ thị vô hướng Vô hướng Không Không
Đa đồ thị vô hướng Vô hướng Không
Giả đồ thị vô hướng Vô hướng
Đồ thị có hướng Có hướng Không
Đa đồ thị có hướng Có hướng

*Hai đỉnh u và v của đồ thị vô hướng G =<V, E> được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G. Nếu e =(u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là đỉnh đầu của cạnh (u,v).

*Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và ký hiệu là deg(v).

deg(a) = 2, deg(b) =deg(c) = deg(f) = 4, deg(e) = 3, deg(d) = 1, deg(g)=0.

Đồ thị có hướng G

Đồ thị có hướng G

Nếu e=(u,v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v. Đỉnh u sẽ được gọi là đỉnh đầu v là đỉnh cuối của cung (u,v).

Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) và deg-(v).

deg-(a) = 1, deg-(b) = 2, deg-(c) = 2, deg-(d) = 2, deg-(e) = 2. deg+(a) = 3, deg+(b) = 1, deg+(c) = 1, deg+(d) = 2, deg+(e) = 2.

Đường đi: Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G=<V,E> là dãy: x0, x1,..., xn-1, xn trong đó n là số nguyên dương, x0=u, xn=v, (xi, xi+1)∈E, i =0, 1, 2,..., n-1.

Đường đi như trên còn có thể biểu diễn thành dãy các cạnh:

(x0, x1), (x1,x2),..., (xn-1, xn).

Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào lặp lại.

Đồ thị vô hướng được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Cách phát hiện và khắc phục lỗi SQL injection trong PHP

Cách phát hiện và khắc phục lỗi SQL injection trong PHP

SQL Injection Là một trong những kiểu hack web phổ biến vào những năm trước đây, nhưng mãi cho đến hiện nay vẫn có khá nhiều trang web vẫn mắc lỗi này vì thế trong bài viết này sẽ mô tả về SQL injection và bạn sẽ cảm thấy an tâm hơn khi hiểu rõ về nó.

Drupal Open Atrium 2 đã có bản BETA Time

Drupal Open Atrium 2 đã có bản BETA Time

After nearly a year of planning and development, I finally released the first BETA version of Open Atrium 2 over the weekend. So what’s the big deal with Beta releases? Read on to find out.

Lịch sử phát triển tối ưu hoá công cụ tìm kiếm - SEO

Lịch sử phát triển tối ưu hoá công cụ tìm kiếm - SEO

SEO - Google Yahoo MSN Search Engine Lịch sử phát triển tối ưu hoá công cụ tìm kiếm

Tomdesgin.vn

 

Drupal Services