Bài 2: Khái niệm Graph Theory

Tham khảo Video sau đây :

Sau đây là lý thuyết mình co động lại (không nhất thiết phải xem Video)

1.Định nghĩa

Graph là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó

💡 KÝ HIỆU

G = (V, E), trong đó :

• V là tập đỉnh (vertex)

• E ⊆ V ₓ V là tập hợp các cạnh (edge)

⚠️ LƯU Ý

Có tổng cộng 5 loại đồ thị :

1. Đơn đồ thị (Single Graph)

2. Đa đồ thị (MultiGraph)

3. Giả đồ thị (Pseudo Graph)

4. Đồ thị có hướng (Directed Graph)

5. Đa đồ thị có hướng (Directed MultiGraph)

2.Các loại đồ thị

a.Định nghĩa

Loại	Định nghĩa (G = (V, E))	Mô hình
Đơn đồ thị	Gồm một tập không rỗng V và một tập cạnh E là các cạnh không sắp thứ tự của các đỉnh phân biệt
Đa đồ thị	- Gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E  - Các cạnh e₁, e₂ - Gọi là cạnh song song (parallel) hoặc cạnh bội (multiple) Nếu f(e₁) = f(e₂)
Giả đồ thị	- Gồm một tập các đỉnh V và một tập các cạnh E và một hàm f từ E tới {u, v} trong đó u,v ∈ V - Một cạnh là khuyên (loop) nếu f(e) = {u,u} = {u} với đỉnh u nào đó
Đồ thị có hướng	- Gồm tập các đỉnh V và một tập các cạnh E là các cặp có thứ tự của các phần tử thuộc V - Các cạnh ở đây được gọi là cung (arc)
Đa đồ thị có hướng	- Gồm một tập các đỉnh V và một tập các cạnh E và một hàm f từ E tới {u, v |u,v ∈ V} - Các cạnh e₁ và e₂ là các cạnh bội nếu f(e₁) = f(e₂)

b.Tính chất

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

3.Các loại mô hình đồ thị

Đồ thị	Mô hình	Ví dụ
Quen biết		Trên trái đất có hơn 6 tỉ đỉnh và có thể hơn tỉ tỉ cạnh
Ảnh hưởng		Đỉnh: tác giả Cạnh: 2 người viết chung bài báo ==> Đồ thị cộng tác (2001) có hơn 337000 đỉnh và 496200 cạnh
Thi đấu vòng tròn		Đỉnh: Đội tham gia thi đấu Giữa 2 đỉnh tồn tại đúng 1 cạnh

4.Bài tập ví dụ

a.Xác định loại đồ thị

MẸO GIẢI

Để làm được bài này cần mẹo của mình như sau :

Ta phân ra có khuyên hay không :

• Nếu Có : đơn hoặc đa

  • Kiểm tra có cạnh bội không ?

    • Nếu Có ==> đơn

    • Nếu Không ==> đa

• Nếu Không : gỉa hoặc có hướng hoặc đa có hướng

  • Kiểm tra có cạnh có hướng không ?

    • Nếu Có ==> đơn có hướng và đa có hướng

      • Kiểm tra có cạnh bội không ?

        • Nếu Có ==> đơn có hướng

        • Nếu Không ==> đa có hướng

    • Nếu Không ==> giả

Mô hình	Trả lời	Lý do
	Đơn đồ thị	Không cạnh có hướng, cạnh bội và khuyên
	Đơn đồ thị có hướng	Có khuyên, cạnh có hướng Không cạnh bội
	Giả đồ thị	Có khuyên, cạnh bội Không cạnh có hướng
	Đa đồ thị có hướng	Có cạnh có hướng, cạnh bội và khuyên

b.Xây dựng mô hình

Xây dưng đồ thị ảnh hưởng cho các thành viên lãnh đạo của một công ty nếu :

• Chủ tịch có ảnh hưởng lên giám đốc nghiên cứu và phát triển, giám đốc marketing, giám đốc điều hành

• Giám đốc nghiên cứu và phát triển có ảnh hưởng lên giám đốc điều hành

• Giám đốc Marketing ảnh hưởng lên giám đốc điều hành

• KHÔNG ai có thể ảnh hưởng tới trưởng phòng tài chính

• Trưởng phòng tài chính không ảnh hưởng bất cứ ai

Dữ liệu : chủ tịch, giám đốc nghiên cứu & phát triển, giám đốc marketing, giám đốc điều hành, trưởng phòng tài chính