Views: 974
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]$