BÀI TẬP LÝ THUYẾT ĐỒ THỊ Giảng viên: Nguyễn Ngọc Trung

- BÀI TẬP LÝ THUYẾT ĐỒ THỊ.
- ĐẠI CƯƠNG VỀ ĐỒ THỊ.
- Đồ thị này sẽ có bao nhiêu cạnh nếu số đội là n đội?.
- Hãy xây dựng đồ thị ưu tiên trước sau cho chương trình sau:.
- Có thể tồn tại đơn đồ thị có 15 đỉnh, mỗi đỉnh đều có bậc là 5 không?.
- Cho các đồ thị hãy xác định bậc của các đỉnh của các đồ thị đó..
- Hãy vẽ một đơn đồ thị vô hướng có 5 đỉnh.
- Hỏi đồ thị này phải có bao nhiêu cạnh? Đỉnh còn lại phải có bậc mấy?.
- Cho một đồ thị vô hướng có n đỉnh.
- Hỏi đồ thị này có thể có tối đa bao nhiêu cạnh.
- Xét một đồ thị vô hướng có n đỉnh và m cạnh.
- Gọi k là bậc nhỏ nhất, K là bậc lớn nhất trong đồ thị.
- Cho một đồ thị vô hướng có n đỉnh và 2n cạnh.
- Chứng minh rằng trong đồ thị này luôn tồn tại một đỉnh có bậc không nhỏ hơn 4..
- Chứng minh rằng trong một đơn đồ thị vô hướng nếu không chứa chu trình thì sẽ luôn tồn tại ít nhất hai đỉnh treo..
- Cho một đồ thị có hướng có n đỉnh.
- Có tồn tại đơn đồ thị vô hướng có 5 đỉnh với các số bậc sau đây không? Nếu có, hãy vẽ đồ thị đó..
- Hãy vẽ các đồ thị sau đây:.
- Cho đồ thị sau.
- Hãy cho biết đồ thị này có tất cả bao nhiêu đồ thị con..
- Đồ thị K 3 có bao nhiêu đồ thị con có ít nhất một đỉnh?.
- Một đồ thị được gọi là chính quy nếu mọi đỉnh của nó đều có bậc như nhau.
- Một đồ thị được gọi là n-chính quy nếu mọi đỉnh của nó đều có bậc n..
- Với các giá trị nào của n thì đồ thị sau đây là chính quy?.
- Với các giá trị nào của m, n thì đồ thị K mxn là đồ thị chính quy?.
- Đồ thị bù G của đồ thị G là đồ thị có cùng số đỉnh với G.
- Hãy xác định đồ thị bù của các đồ thị dưới đây:.
- Nếu đồ thị G có n đỉnh và m cạnh thì đồ thị G có bao nhiêu đỉnh, bao nhiêu cạnh?.
- Chứng minh rằng nếu G là đồ thị phân đôi có n đỉnh và m cạnh thì ta có:.
- Cho các đồ thị sau, hãy xác định đồ thị nào là đồ thị phân đôi:.
- Xét đồ thị sau:.
- Cho biết đồ thị này có liên thông mạnh hay liên thông yếu hay không?.
- Hãy tìm số đường đi đơn độ dài n giữa hai đỉnh kề nhau bất kỳ trong đồ thị K 3x3 với:.
- Chứng minh rằng đồ thị vô hướng liên thông G có n đỉnh thì sẽ có ít nhất n – 1 cạnh..
- Chứng minh rằng trong một đơn đồ thị sẽ luôn tồn tại ít nhất 2 đỉnh không là đỉnh cắt..
- Chứng minh rằng một cạnh trong đơn đồ thị là cạnh cắt nếu và chỉ nếu nó không nằm trong bất kỳ chu trình nào của đồ thị..
- Xét một đồ thị vô hướng có k thành phần liên thông.
- Chứng minh rằng số cạnh của đồ thị này không thể vượt quá.
- BIỂU DIỄN ĐỒ THỊ.
- Xác định ma trận kề của các đồ thị sau đây:.
- Hãy xác định ma trận liên thuộc của các đồ thị trên 34.
- Hãy xác định danh sách cạnh của các đồ thị trên 35.
- Hãy xác định danh sách kề của các đồ thị trên 36.
- Gọi A là ma trận kề của đồ thị bên..
- Nếu hai đồ thị đẳng cấu với nhau thì ma trận kề của chúng có giống nhau hay không? Tại sao?.
- Cho hai đồ thị có cùng 5 đỉnh.
- Vậy hai đồ thị có chắc chắn đẳng cấu với nhau hay không.
- Có tất cả bao nhiêu đồ thị có 5 đỉnh và 2 cạnh.
- Trong số đó có bao nhiêu đồ thị đẳng cấu với nhau..
- Nêu đặc điểm của ma trận kề của các đồ thị sau:.
- Đồ thị đầy đủ.
- Đồ thị phân đôi đầy đủ K 1xn.
- Hãy vẽ các đồ thị được biểu diễn bởi các ma trận kề dưới đây.
- Hãy cho biết chúng là đồ thị có hướng hay vô hướng:.
- Một đơn đồ thị được gọi là tự bù nếu và chỉ nếu G và G là đẳng cấu..
- Hãy tìm một đồ thị tự bù có 5 đỉnh.
- Với số nguyên nào của n thi C n là đồ thị tự bù..
- Chứng minh rằng nếu G là đồ thị tự bù với n đỉnh thì hoặc n chia hết cho 4, hoặc n chia 4 dư 1..
- Hãy xác định các đồ thị sau có đẳng cấu hay không.
- Chứng minh răng một đồ thị vô hướng, liên thông có n đỉnh và n-1 cạnh thì sẽ không thể chứa chu trình nào..
- Các đồ thị sau đây có phải là đ.
- Các đồ thị trên đây có phải là đ là Hamilton hay nửa Hamilton thì ph 50.
- Cho đồ thị vô hướng liên thông.
- Đồ thị Euler b.
- Đồ thị nửa Euler 52.
- Hãy vẽ tất cả các đồ thị vô hư.
- Ồ THỊ EULER – ĐỒ THỊ HAMILTON.
- t đồ thị vô hướng, luôn tồn tại đường đi đơn từ khác..
- i là đồ thị Euler hay nửa Euler hay không? Giải thích.
- i là đồ thị Hamilton hay không? Chứng minh..
- t đồ thị vô hướng n đỉnh, luôn tồn tại hai đỉnh có b u G là đồ thị Hamilton thì G sẽ không chứa đỉnh cắt nào..
- u G là đồ thị Euler thì G sẽ không chứa cạnh cắt (cầu) nào..
- ng minh rằng đồ thị n còn liên thông).
- ĐỒ THỊ PHẲNG – BÀI TOÁN TÔ MÀU ĐỒ THỊ.
- Xét một đồ thị liên thông có 8 đỉnh bậc 3.
- Hỏi biểu diễn phẳng của đồ thị này sẽ chia mặt phẳng thành mấy miền..
- Các đồ thị sau đây có là đồ thị phẳng không? Nếu có hãy vẽ biểu diễn phẳng của nó.
- Xét một đơn đồ thị phân đôi, phẳng, liên thông có e cạnh và v đỉnh (v3).
- Một đồ thị vô hướng, phẳng có e cạnh, v đỉnh và k thành phần liên thông.
- Hãy tìm biểu thức quan hệ giữa r – số miền trong biểu diễn phẳng của đồ thị – với e, v và k..
- Hãy xây dựng đồ thị đối ngẫu với các bản đồ dưới đây.
- Hãy tìm số màu của các đồ thị dưới đây:.
- Chứng minh rằng nếu đồ thị G có chứa một chu trình có độ dài lẻ thì số màu của G ít nhất phải là 3..
- Tính số màu của các đồ thị sau:.
- Chứng minh rằng một đơn đồ thị vô hướng là phân đôi nếu và chỉ nếu số màu của nó là 2..
- Số màu cạnh của một đồ thị là số màu ít nhất dùng để tô màu các cạnh của đồ thị..
- Hãy xác định số màu cạnh của các đồ thị trong bài 66..
- Hãy đưa bài toán tô màu cạnh về bài toán tô màu đồ thị (tô màu đỉnh).
- Cho G là đồ thị vô hướng liên thông có n đỉnh và m cạnh.
- Hãy vẽ tất cả các cây khung của các đồ thị sau:.
- Các đồ thị sau có tất cả bao nhiêu cây khung?.
- Hãy tìm cây khung nhỏ nhất của các đồ thị sau bẳng thuật toán Prim:.
- Hãy đề xuất hai thuật toán để tìm cây khung cực đại của một đồ thị..
- Áp dụng các thuật toán trên để tìm cây khung cực đại của hai đồ thị trong bài 82..
- Hãy tìm cây khung nhỏ nhất của các đồ thị sau bẳng thuật toán Prim:\.
- Hãy áp dụng thuật toán Kruskal để tìm cây khung nhỏ nhất của các đồ thị trong bài 86..
- Hãy áp dụng thuật toán Ford-Bellman để tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác trong các đồ thị dưới đây.
- Hãy áp dụng thuật toán Dijsktra để tìm đường đi ngắn nhất từ a tới z trong đồ thị ở bài 88, câu b, biết rằng đường đi này phải đi qua đỉnh f..
- Cho G là một đồ thị có trọng số và u* là một đỉnh của G.
- Cho G là một đồ thị có trọng số và (u*, v*) là một cạnh của G

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt