Lý thuyết đồ thị

Dạng 1. Đồ thị vô hướng

1.Định nghĩa: Đơn đồ thị vô hướng ? = (?,?) 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 (không kể thứ tự)

2. Bài tập

Bài 1. Cho đồ thị vô hướng (không có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0\end{array}\right]


Bài 2. Cho đồ thị vô hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0\end{array}\right]

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 3 & 0 & 1 & 0 & 0 \\ 3 & 0 & 5 & 2 & 0 & 0 \\ 0 & 5 & 0 & 0 & 4 & 2 \\ 1 & 2 & 0 & 0 & 6 & 0 \\ 0 & 0 & 4 & 6 & 0 & 7 \\ 0 & 0 & 2 & 0 & 7 & 0\end{array}\right]


Bài 3. Cho đồ thị vô hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0\end{array}\right]

 

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 2 & 0 & 3 & 0 & 0 \\ 2 & 0 & 7 & 2 & 1 & 0 \\ 0 & 7 & 0 & 0 & 0 & 3 \\ 3 & 2 & 0 & 0 & 2 & 0 \\ 0 & 1 & 0 & 2 & 0 & 4 \\ 0 & 0 & 3 & 0 & 4 & 0\end{array}\right]


Bài 4. (Đề thi HK3 năm 2022) Cho đồ thị vô hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0\end{array}\right]

 

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 2 & 0 & 5 & 0 & 0 \\ 2 & 0 & 8 & 1 & 0 & 0 \\ 0 & 8 & 0 & 0 & 2 & 1 \\ 5 & 1 & 0 & 0 & 3 & 0 \\ 0 & 0 & 2 & 3 & 0 & 5 \\ 0 & 0 & 1 & 0 & 5 & 0\end{array}\right]


 


Dạng 2. Đồ thị có hướng

1. Định nghĩa: Đơ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 (có thứ tự)

+Xét đồ thị đơn vô hướng G=(V, E), với tập đỉnh V=\{1,2, \ldots, n\}, tập cạnh E=\left\{e_{1}, e_{2}, \ldots, e_{m}\right).
Ta gọi ma trận kề của đồ thị G là ma trận có các phần tử bằng 0 hoặc 1

A=\left\{a_{i j}: a_{i j}=1 \right. nếu (i, j) \in E, a_{i j}=0 nếu \left.(i, j) \notin E ; i, j=1,2, \ldots, n\right\}.

 

2. Bài tập:

Bài 5. Cho đồ thị có hướng (không có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]


 

Bài 6. Cho đồ thị có hướng (không có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllllll}0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]


Bài 7. Cho đồ thị có hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 3 & 0 & 4 & 0 & 0 \\ 0 & 0 & 6 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 4 & 3 \\ 0 & 0 & 1 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]


Bài 8. Cho đồ thị có hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 2 & 0 & 5 & 0 & 0 \\ 0 & 0 & 7 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 6 & 0 \\ 0 & 0 & 3 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]


Bài 8. Cho đồ thị có hướng (có trọng số)

Biểu diễn bằng ma trận kề

\left[\begin{array}{llllll}0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]

Biểu diễn bằng ma trận KHOẢNG CÁCH

\left[\begin{array}{llllll}0 & 3 & 0 & 1 & 0 & 0 \\ 0 & 0 & 7 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 \\ 0 & 0 & 9 & 0 & 2 & 0 \\ 0 & 0 & 3 & 0 & 0 & 7 \\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *