tailieunhanh - Bài giảng học Lý thuyết đồ thị

lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh). | Lý thuyết đồ thị Chương 1: Giới thiệu Chương 1: Giới thiệu Định nghĩa: Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp các đỉnh (vertices) V (V Ø) và các cạnh (edges) E. Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên kết hay kề (adjacent) với nhau và e được gọi là tới các đỉnh v, w. Ký hiệu hay v w. e Chương 1: Giới thiệu Các đỉnh: A, B, C, D Các cạnh: AB, AC, AD, BD, BC A B C D Cạnh không phân biệt thứ tự của đỉnh được gọi là cạnh vô hướng. Đồ thị bao gồm các cạnh vô hướng được gọi là đồ thị vô hướng. Chương 1: Giới thiệu Định nghĩa: Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi là vòng (loop) hay khuyên. A B C Chương 1: Giới thiệu Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh gọi là 2 cạnh song song (parallel edge). A B C Chương 1: Giới thiệu Đồ thị không có cạnh song song và khuyên được gọi là đơn đồ thị (simple graph), ngược lại là đa đồ thị (multi graph). A B C A B C D Chương 1: Giới thiệu Đồ thị G’ = (V’, E’) gọi là 1 đồ thị con (sub graph) của đồ thị G = (V, E) nếu V’ V và E’ E. A B C D E B’ C’ A’ E’ Chương 1: Giới thiệu Đồ thị có số đỉnh và số cạnh hữu hạn gọi là đồ thị hữu hạn (finite graph), ngược lại là đồ thị vô hạn (infinite graph). Chương 1: Giới thiệu Biểu đồ A B C D A’ B’ C’ D’ E’ A” B” C” Chương 1: Giới thiệu Bậc của một đỉnh Bậc (degree) của một đỉnh v, ký hiệu là d(v), chính là số cạnh tới đỉnh đó. Mỗi vòng tại một đỉnh sẽ được xem như 2 cạnh tới đỉnh đó. Nếu d(v) = 0, v được gọi là đỉnh cô lập (isolated vertex). Nếu d(v) = 1, v được gọi là đỉnh treo (perdant vertex), cạnh tới đỉnh treo được gọi là cạnh treo (perdant edge). Đồ thị mà mọi đỉnh đều là đỉnh cô lập được gọi là đồ thị rỗng (null graph). Chương 1: Giới thiệu Bậc của các đỉnh: A: 2 B: 5 C: 0 (đỉnh cô lập) D: 2 E: 1 (đỉnh treo) F: 4 A B C D E F X Y Z T G G’ Chương 1: Giới thiệu Đồ thị mà mọi cặp đỉnh đều kề nhau được gọi là đồ thị đầy . | Lý thuyết đồ thị Chương 1: Giới thiệu Chương 1: Giới thiệu Định nghĩa: Đồ thị (graph) G = (V,E) là một bộ gồm 2 tập hợp các đỉnh (vertices) V (V Ø) và các cạnh (edges) E. Mỗi cạnh tương ứng với 2 đỉnh. Nếu cạnh e tương ứng với 2 đỉnh v, w thì ta nói v và w là 2 đỉnh liên kết hay kề (adjacent) với nhau và e được gọi là tới các đỉnh v, w. Ký hiệu hay v w. e Chương 1: Giới thiệu Các đỉnh: A, B, C, D Các cạnh: AB, AC, AD, BD, BC A B C D Cạnh không phân biệt thứ tự của đỉnh được gọi là cạnh vô hướng. Đồ thị bao gồm các cạnh vô hướng được gọi là đồ thị vô hướng. Chương 1: Giới thiệu Định nghĩa: Cạnh uv tương ứng với 2 đỉnh trùng nhau gọi là vòng (loop) hay khuyên. A B C Chương 1: Giới thiệu Hai cạnh phân biệt cùng tương ứng với một cặp đỉnh gọi là 2 cạnh song song (parallel edge). A B C Chương 1: Giới thiệu Đồ thị không có cạnh song song và khuyên được gọi là đơn đồ thị (simple graph), ngược lại là đa đồ thị (multi graph). A B C A B C D .