# Định nghĩa
- ĐỒ THỊ VÔ HƯỚNG
G=(V,E) gồm:
V là tập các đỉnh;
E là tập các cạnh không sắp thứ tự của 2 phần tử thuộc V, gọi là cạnh của G.
Hai cạnh nối cùng cặp đỉnh là cặp cạnh song song.
Đồ thị vô hướng có 3 loại:
1. Đơn đồ thị: chỉ gồm các cạnh đơn.
2. Đa đồ thị: có các cặp cạnh song song, không có khuyên.
3. Giả đồ thị: có các cặp cạnh song song + khuyên.

- ĐỒ THỊ CÓ HƯỚNG
G=(V,E) gồm:
V là tập các đỉnh;
E là tập các cạnh có hướng (cung); vd (a,b) thì từ a->b.
Nếu uv là 1 cung:
-> u, v kề nhau, trong đó u là đỉnh đầu (gốc), v là đỉnh cuối (ngọn); đỉnh v là đỉnh sau của đỉnh u.
Hai cung có cùng gốc và ngọn gọi là cung song song.
Cung có điểm gốc và ngọn trùng nhau gọi là khuyên.
Đồ thị có hướng có 2 loại:
1. Đơn đồ thị: chứa khuyên nhưng không chứa cặp cung song song.
2. Đa đồ thị: chứa cả khuyên + các cặp cung song song.

# Bậc của các đỉnh
- ĐỒ THỊ VÔ HƯỚNG:
Bậc của đỉnh là số cạnh kề với đỉnh đó (nối vs đỉnh đó).
Nếu đỉnh có khuyên thì bậc +2.
KH: deg(a) - bậc của đỉnh a.

**Tổng bậc của tất cả các đỉnh = 2m** ; (m là số cạnh của đồ thị).

- ĐỒ THỊ CÓ HƯỚNG:
deg+(a) - số cung đi ra từ đỉnh a/ có gốc là đỉnh a; gọi là bậc ra của a.
deg-(a) - số cung đi vào đỉnh a/ có ngọn là đỉnh a; gọi là bậc vào của a.


deg (a) = deg+(a) + deg-(a);

Công thức số cạnh:
**m = tổng deg-() = tổng deg+();**

Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 gọi là đỉnh treo


# Biểu diễn ma trận của đồ thị
(phần này t thấy ko quan trọng lắm ấy, nhưng cứ đọc cho biết)
- **Ma trận kề:**
Cho G có tập các đỉnh là {a,b,c,d}
Vẽ một ma trận vs hàng ngang và dọc đều có 4 đỉnh.
Tại ô nào của ma trận có hai cạnh kề nhau thì đánh số là số cạnh nối hai 2 đỉnh đó.

Nếu giả sử cặp đỉnh a-c có cặp cạnh song song thì ma trận sẽ thành
hay một ví dụ khác
- **Đẳng cấu**
hiều đơn giản là từ một đồ thị, ta có thể vẽ lại nó theo hình dạng khác nhưng mối liên hệ, cạnh kề, đỉnh kề và số bậc của các đỉnh không thay đổi.

# Đường đi, chu trình và đồ thị liên thông.
1. u và v liên thông với nhau khi và chỉ khi có đường đi từ u đến v và ngược lại.
2. Mỗi lớp tương đương (chương quan hệ ??? t nghĩ thế) được gọi là một thành phần liên thông của đồ thị(G).
3. Nếu G chỉ có một thành phần liên thông thì G liên thông.
trong hình này G có 3 thành phần liên thông.

G liên thông.

- **Đỉnh khớp**:
v4 là đỉnh khớp
vì khi xóa v4, các cạnh nối vs v4 cũng sẽ bị xóa. Khi đó đồ thị không còn liên thông nữa.

- **Cầu**:
AD(màu đỏ) là cầu
vì khi đồ thị thiếu AD đó thì không liên thông.

- **Đường đi**: là đường gồm các đỉnh và các cạnh đi từ u đến v.
a) Đường đi không có cạnh nào xuất hiện quá một lần gọi là **đường đi đơn** (giống đường đi *Euler*)
b) Đường đi không có đỉnh nào xuất hiện quá một lần gọi là **đường đi sơ cấp** (giống đường đi *Hamilton*)
c) Đường đi được gọi là **chu trình** nếu nó bắt đầu và kết thúc tại cùng một đỉnh
Chu trình sơ cấp: là chu trình không chứa cùng một đỉnh quá một lần (trừ đỉnh đầu và đỉnh cuối). Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình sơ cấp. Chu trình sơ cấp thì là chu trình đơn.

đường đi có chứa n đỉnh thì sẽ có n-1 cạnh.
-> đường đi có độ dài chẵn -> n-1 chẵn -> số đỉnh lẻ.
và ngược lại.

điều này thì đường đi khác vs chu trình.
chu trình có độ dài n thì có số cạnh = số đỉnh = n.

- **Chu trình**:
Trong lý thuyết đồ thị, chu trình trong đồ thị là một dây chuyền đóng.

Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là đồ thị vòng, ký hiệu Cn,

Các loại chu trình:

Chu trình **chẵn**: là chu trình có độ dài chẵn.
Chu trình **lẻ**: là chu trình có độ dài lẻ.
Chu trình **có hướng**: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là chu trình khi ngữ cảnh rõ ràng.
Chu trình **đơn**: là chu trình không đi qua một cạnh nào quá một lần.
Chu trình **sơ cấp**: là chu trình không chứa cùng một đỉnh quá một lần (trừ đỉnh đầu và đỉnh cuối). Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình sơ cấp. Chu trình sơ cấp thì là chu trình đơn.
Chu trình **Euler**: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
Chu trình **bao trùm**: là cách gọi khác của chu trình Hamilton.

# Một số đồ thị vô hướng đặc biệt:
1. Đồ thị đủ cấp n: Kn
là đơn đồ thị cấp n mà giữa hai đỉnh bất kỳ đều có một cạnh.

2. Đồ thị k-đều: là đồ thị mà mọi đỉnh đều có bậc bằng nhau và bằng k.
vd; đồ thì đầy đủ cấp n cx là một đồ thì k-đều vs k=n-1.

3. Đồ thị lưỡng phân:
G = (V,E), tập đỉnh V được chia thành hai tập đỉnh con nhỏ hơn V1 và V2.
Mọi cạnh của G đều nối một đỉnh trong V1 với một đỉnh trong V2; hai đỉnh trong cùng 1 tập V1 hoặc V2 không nối vs nhau.

4. Đồ thị lưỡng phân đủ: là đồ thị đơn, lưỡng phân, mỗi đỉnh trong V1 đều kề với mọi đỉnh trong V2.
KH: K2,3

5. Đồ thị bù. Cho Kn = (V,E), G (V,E1) gọi là đồ thị bù của G.
Đồ thị G đươc gọi là tự bù nếu G đẳng cấu với đồ thị bù của nó. kiểu 1/2 + 1/2 = 1 ấy

**MỘT SỐ ĐỒ THỊ ĐẶC BIỆT **
số cạnh của Cn là n cạnh.

Wheels Wn.
số cạnh 2(n-1).

số cạnh khó chưa nghĩ ra

# Đồ thị phẳng
Một đồ thị được gọi là một đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh.
Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị. Ví dụ K4 (W4) là một đồ thị phẳng.
nhớ lại bài toán giếng nước.

- Miền: số cạnh của đồ thị phân mặt phẳng thành các miền, với biên giới là cạnh. (r - là số miền).

- Công thức Euler: liên hệ m (số cạnh), n (số đỉnh), r(số miền):

r = m - n + 2;

Hệ quả : điều kiện để là đồ thị phẳng:

3/2*f <= m <= 3n-6

Ứng dụng của đồ thị: thông qua bài toán tô màu

# Bài toán tô màu:
**Nguyên lý cơ bản**: những đỉnh kề nhau thì khác màu nhau.
bài này có thuật toán nhưng mà t thấy đọc khó hiểu ấy, t sẽ nói cách t làm, tô màu lần lượt.

Đầu tiên chọn đỉnh nào bậc cao nhất - tạm gọi đỉnh a (kề nhiều cạnh nhất) tô màu trc, màu (1).

sau đấy thì đỉnh nào bậc cao tiếp theo m tô màu tiếp:
- nếu mà nó kề vs a thì để màu (2).
- nếu ko thì m để màu (1).

xong cứ thế tiếp tục tô theo đỉnh có bậc giảm dần, nếu kề vs các đỉnh có màu 1, màu 2 thì lấy màu 3.

nhớ là dùng ít màu nhất có thể.

Số màu ít nhất có thể để tô một đồ thị gọi là sắc số.
KH: S(G)=k ; k là số màu.

**Định lý**:
1. Chu trình có độ dài chẵn (n=2k) có sắc số = 2;
Chu trình có độ dài lẻ có sắc số = 3

2. Định lý G có ít nhất 1 cạnh là đồ thị 2 sắc khi và chỉ khi không có chu trình có độ dài lẻ.

3. Đồ thị đầy đủ n đỉnh Kn luôn có sắc số bằng n.

4. Định lý 4 màu: số màu của đồ thị phẳng không bao giờ lớn hơn 4.

Ứng dụng: tô màu bản đồ (mỗi vùng là 1 đỉnh, có chung ranh giới thì có cạnh nối vs nhau) ;
lập lịch thi (đỉnh là môn thi; 2 môn có sinh viên thi chung thì có cạnh nối, số đợt thi là sắc số);
phân chia tần số (bài hóa chất: đỉnh là hóa chất, phản ứng vs nhau thì có cạnh nối với nhau).

# Đường đi, chu trình Euler.
VÔ HƯỚNG:
**Đường đi Euler** là đường đi đi qua mỗi cạnh một lần.
Điều kiện tồn tại: G có 2 đỉnh bậc lẻ và mọi đỉnh khác là bậc chẵn.

**Chu trình Euler** là chu trình đi qua mỗi cạnh một lần.
(chu trình đơn)
Điều kiện tồn tại: G có mọi đỉnh đều bậc chẵn.
-> G có chu trình Euler thì G là đồ thị Euler.

CÓ HƯỚNG:
G cân bằng <=> G có hướng, liên thông, có chu trình Euler. ???(trong vở ghi deg- = deg+)


# Đường đi, chu trình Hamilton