Câu hỏi:
26/06/2024 18Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau:
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Bộ dữ liệu biểu diễn cho hai đồ thị:
Đồ thị (a):
n (số đỉnh): 4
V (tập hợp đỉnh): {a, b, c, d}
E (tập hợp cạnh): {(a,b), (a,c), (a,d), (b,c), (c,d)}
A (ma trận kề): Chưa được xác định trong hình ảnh
Adj (danh sách kề):
Đỉnh a: {b, c, d}
Đỉnh b: {a, c}
Đỉnh c: {a, b, d}
Đỉnh d: {a, c}
Đồ thị (b):
n: 6
V: {0, 1, 2, 3, 4, 5}
E: {(0,1), (0,5), (1,2), (1,4), (2,3), (3,4), (4,5)}
A: Chưa được xác định trong hình ảnh
Adj:
Đỉnh 0: {1, 5}
Đỉnh 1: {0, 2, 4}
Đỉnh 2: {1, 3}
Đỉnh 3: {2, 4}
Đỉnh 4: {1, 3, 5}
Đỉnh 5: {0, 4}
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.
Câu 2:
Vẽ đồ thị vô hướng G = (V, E) sau:
V = [0, 1, 2, 3, 4]
E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}]
Câu 4:
Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.
Câu 5:
1. Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị và trả lời câu hỏi: Bài toán trong phần khởi động có thể biểu diễn được bằng mô hình đồ thị không?
2. Em hãy tìm một số bài toán thực tế khác có thể biểu diễn được bằng đồ thị.
Câu 6:
Câu 7:
Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần.
Em hãy giải bài toán trên.
Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?
về câu hỏi!