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).
Nội dung trích xuất từ tài liệu:
Bài giảng học Lý thuyết đồ thịLýthuyếtđồthịChương1:Giớithiệu 1Chương1:Giớithiệ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ý e = vw hay v e w. hiệu 2Chương1:Giớithiệu A Các đỉnh: A, B, C, D  Các cạnh: AB, AC, AD,  BD, BC B D C 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. 3Chương1:Giớithiệ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. B A C 4Chương1:Giớithiệ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). B A C 5Chương1:Giớithiệ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). B A B A C C D 6Chương1:Giớithiệ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 A’ E’ B’ E B C’ D C 7Chương1:Giớithiệ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). 8Chương1:Giớithiệu Biểu đồ A’ A B B’ A” C’ E’ D C B” C” D’ 9 Chương1:Giớithiệ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). 10Chương1:Giớithiệu Bậc của các đỉnh:  A B C A: 2G B: 5 F D C: 0 (đỉnh cô lập) E D: 2 Y X E: 1 (đỉnh treo) F: 4G’ Z T 11Chương1:Giớithiệu Đồ thị mà mọi cặp đỉnh đều kề nhau được- gọi là đồ thị đầy đủ (complete graph). Đồ thị đầy đủ có n đỉnh được ký hiệu là Kn. A E B D C 12Chương1:Giớithiệu Đồ thị bù của một đồ thị G, ký hiệu là G, là- một đồ thị có cùng đỉnh với G và có các cạnh là những cạnh mà ta phải bổ sung vàođể G trở thành đầy đủ. G G 13Chương1:Giớithiệu Định lý 1.1: Với mọi đồ thị G = (V, E), ta có: ∑d (v) = 2 E v∈V Hệ quả 1.1: Tổng số bậc của các đỉnh bậc lẻ trong 1 đồ thị là 1 số chẵn Hệ quả 1.2: Mọi đồ thị đều có một số chẵn các đỉnh bậc l ẻ. 14Chương1:Giớithiệu Hệ quả 1.3: 1 Đồ thị Kn có n(n-1) cạnh. ...