TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 4: Cây

Nội dung chương này trình bày định nghĩa và các tính chất cơ bản của cây; tìm cây bao trùm theo phương pháp – DFS (Depth First Search); cây bao trùm nhỏ nhất và một số nội dung khác. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết. | Bài giảng LÝ THUYẾT ĐỒ THỊ GRAPH THEORY TRẦN QUỐC VIỆT 05 11 2013 1. Định nghĩa và các tính chất cơ bản Định lý 1 Giữa 2 đỉnh bất kỳ trong cây T luôn có một và chỉ một đường đi trong T nối chúng c m. Xét 2 đỉnh X y bất kỳ trong T x y Do T liên thông nên có đường đi nối X và y Giả sử có ít nhất 2 đường đi khác nhau giữa và y lyx-VọXb .VpVịm y Vj VpVj 1 y o- Ỵj 1 oy Tồn tại chu trình x v0 Vi K mâu thuân với gt v2 4 1 Định nghĩa và các tính chất cơ bản tt Định nghĩa Cây có gốc rooted tree là một cây có hướng trên đó đã chọn một đỉnh là gốc root của cây và các cạnh định hướng sao cho với mọi đỉnh luôn có một đường đi từ gốc đến đỉnh đó Định nghĩa và các tính chất cơ bản tt Định nghĩa Tập họp các cây đôi một không có đỉnh chung gọi là một rừng Forest một rừng forest gồm nhiều cây không có đỉnh chung Mọi đỉnh X trong một cây mà là gốc của một cây con Khi xóa đỉnh X khỏi cây ta được một rừng 05 11 2013 Định nghĩa và các tính chất cơ bản tt Xét xây có gốc T - Mức của đỉnh Khoảng cách từ gốc đến nút đó - Chiều cao của cây Mức lớn nhất của một đỉnh bất kỳ root Mức 3 Mức 0 Mức 1 Mức 2 - Nếu xy là cạnh của T ta gọi X đỉnh cha parent của y y là đỉnh con child của X - Lá leaves Những đỉnh không có cây con. - Đỉnh trong internal vertices là những đỉnh có ít nhất 1 cây con Định nghĩa và các tính chất cơ bản tt Định lý 2 Nếu một cây có n đỉnh thì sẽ có m n-1 cạnh c m Ta chọn một nút làm gốc để được cây có gốc Với cây chỉ có 1 đỉnh n l số cạnh là 0 nghĩa là m n-l Giả sử cây có k đỉnh thì có k-1 cạnh là đúng Xét cây có k 1 đỉnh và xét một đỉnh lá V bất kỳ nếu loại bỏ V cùng với cạnh nối đến V chỉ có duy nhất 1 cạnh nối đến v đồ thị T còn lại cũng là một cây có k đỉnh T có k-1 cạnh T có k cạnh Theo nguyên lý quy nạp một cây có n đỉnh thì sẽ có m n-l cạnh đúng với mọi n n l 2 Định nghĩa và các tính chất cơ bản tt Xét xây có gốc T - Đỉnh có độ lệch tâm nhỏ nhất gọi là tâm center của T - Độ lệch tâm của tâm gọi là bán kính radius của T 05 11 2013 Định nghĩa và các tính chất cơ

• Toán học
• Lý thuyết đồ thị
• Bài giảng lý thuyết đồ thị
• Bài toán lý thuyết đồ thị
• Định nghĩa cây
• Cây bao trùm nhỏ nhất
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị