# Các khái niệm cơ bản của lí thuyết đồ thị
## (Toán rời rạc)
**Các khái niệm cơ bản về lý thuyết đồ thị**
+ Đồ thị gồm đỉnh và cạnh (khác với đại số chúng ta thường học trên trường)
### 1. Đơn đồ thị vô hướng
* Thông thường đồ thị hay được kí hiệu bằng chữ G (viết tắt cho chữ Graph)
* Người ta hay cho G = <V,E> trong đó V là tập hợp các đỉnh có trên đồ thị và E là tập hợp các cạnh.
* Đơn : giữa 2 đỉnh chỉ tồn tại tối đa là 1 cạnh
* Vô hướng : không có hướng, không có thứ tự. Bạn cứ tưởng tượng như đây là độ lớn của AB chứ không bao gồm hướng của AB.
* Cạnh là cạnh đơn
### 2.Đa đồ thị vô hướng
Giống đơn đồ thị vô hướng những giữa 2 đỉnh có thể tồn tại nhiều cạnh.
### 3. Giả đồ thị vô hướng
Cái cạnh nối giữa 2 đỉnh không cần nhất thiết là 2 đỉnh khác nhau, người ta gọi cạnh đấy là *"cạnh khuyên"*
=> khi đó không còn là đa đồ thị mà là giả đồ thị (ít dùng)
### 4. Đơn đồ thị có hướng
* Giống đơn đồ thị vô hướng
* Nhưng khác ở chỗ là có hướng. Nghĩa là các cạnh thì có thứ tự, các bạn cứ nhớ đến vector là hiểu. lúc này cạnh không còn vô hướng nữa mà giống như vector vậy.
### 5. Đa đồ thị có hướng
Giống đơn đồ thị có hướng nhưng giữa các đỉnh có thể tồn tại nhiều cạnh. Nếu 2 hay n cạnh có cùng điểm đầu và điểm cuối thì ta gọi đó là *cung lặp*
> (biết thì tốt hơn)
### 6. Đỉnh kề, cạnh liên thuộc.
* Đỉnh kề nói cho dễ hiểu là 2 đỉnh đứng gần nhau nhất, nghĩa là chúng nó chỉ được nối với nhau bởi một cạnh chứ không qua một đỉnh khác.
* Cạnh liên thuộc: Ví dụ có một cạnh nối điểm A và điểm F thì AF là cạnh liên thuộc với 2 đỉnh A,F
### 7.Bậc của đỉnh ở trên đồ thị vô hướng
* Là số cạnh liên thuộc với cái đỉnh đó.
* Hay được kí hiệu là deg. Ví dụ deg(u) là số cạnh liên thuộc của cái đỉnh u. Nói nôm na là đếm xem từ đỉnh u đó có bao nhiêu cạnh đi ra tới các đỉnh khác trong đồ thị.
> **Lưu ý: Chỉ áp dụng với đồ thị vô hướng.**
* Hiểu nôm na thì nó giống như kiểu có bao nhiêu cái cạnh nối tới cái đỉnh đó thì đó là số bậc của đỉnh đó.
* Đỉnh có bậc 0 được gọi là đỉnh cô lập ( đứng một mình không nối với ai)
* Đỉnh có bậc 1 được gọi là đỉnh treo
*
***Định lí: đồ thị G là đồ thị vô hướng có m cạnh, khi đó tổng bậc của các đỉnh trên đồ thị bằng 2 lần số cạnh ( 2*m)***
### 8.Bán bậc vào của đỉnh trên đồ thị có hướng
* Bán bậc ra: deg+(u) -> số cung của đồ thị đi ra khỏi đỉnh u
* Bán bậc vào: deg-(u) -> số cung của đồ thị đi ra vào đỉnh u
*Ví dụ đỉnh A có 3 cung ra và không có cung nào vào cả -> A(3,0).*

**Định lí: Trên đồ thị có hướng, tổng bán bậc ra(deg+(u))= tổng bán bậc vào(deg-(u)) ,của các đỉnh và bằng số lượng cạnh.**
### 9. Đường đi
Bạn cứ tưởng tượng đường đi trong thành phố của bạn, mỗi khu vực sẽ là một đỉnh, mỗi khu vực sẽ có một hoặc nhiều con đường đến đỉnh khác. Thì đó chính là đường đi. Nếu giữa 2 khu vực ( 2 đỉnh) không có bất kì đường đi nào(không có cạnh nối) thì giữa 2 đỉnh đó sẽ không có đường đi

Đường đi đơn: các đỉnh trên đường đi là phân biệt(A,B,C,D) là 1 đường đi đơn, (A,B,C,A,D) là đường đi luôn nhưng không là đơn.
### 10.Chu trình
Cũng là đường đi, gồm các cạnh phân biệt và có đỉnh đầu trùng đỉnh cuối.

Ví dụ(A,B,C,E,D,A) là một chu trình. Bạn tưởng tượng giống như bạn đi 1 tour du lịch vậy, bạn đi qua rất nhiều điểm rồi cuối cùng cũng trở về điểm xuất phát để về nhà phải không?

**Chu trình đơn:** Ngoại trừ đỉnh đầu và đỉnh cuối, còn lại không còn đỉnh nào giống nhau. Ví dụ: (A,B,C,E,D,A) là một chu trình đơn còn (D,A,B,E,F,A,D) là một chu trình nhưng không là chu trình đơn.
### 11.Liên thông
Một đồ thị vô hướng được gọi là liên thông nếu luôn luôn tìm được đường đi giữa 2 đỉnh bất kì của đồ thị.

Nói nôm na là các đỉnh của đồ thị sẽ tạo thành một khối thống nhất, luôn luôn nối với nhau, luôn luôn tìm được cách đi giữa 2 đỉnh bất kì, giống như bạn ở trong một thành phố thì nguyên cái thành phố đó là một đồ thị liên thông vì bạn luôn tìm được đường đi giữa quận này và quận khác, giữa khu vực này là quận khác. Nhưng khi bạn muốn đi từ thành phố ra đảo thì một đồ thị chứa cái đảo đó tách biệt ra thì là không liên thông.
### 12. Thành phần liên thông.
Trong trường hợp đồ thị vô hướng không liên thông thì nó sẽ phân rã thành các "thành phần liên thông"(TPLT).
Vậy suy ra đồ thị vô hướng sẽ liên thông nếu nó có số TPLT = 1.

***Lưu ý:*** 1 đỉnh bị cô lập cũng được tính là 1 TPLT.
> (sẽ hay có bài toán đếm xem có bao nhiêu thành phần liên thông)
### 13. Liên thông mạnh, yếu (áp dụng trên đồ thị có hướng)
***Liên thông mạnh:*** đồ thị có hướng sẽ được gọi là liên thông mạnh nếu giữa 2 đỉnh bất kì luôn có đường đi.

***Liên thông yếu:*** đồ thị có hướng sẽ được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng của nó liên thông.

> Lưu ý: đồ thị đã liên thông mạnh thì chắc chắn sẽ là liên thông yếu nhưng liên thông yếu chưa chắc đã là liên thông mạnh.