Lý thuyết đồ thị - Chương 1: Giới thiệu

Định nghĩa:Đồ thị (graph) G = (V,E) là một bộ gồm 2 tậphợ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ì tanó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 e = v w hay v e w
Nội dung trích xuất từ tài liệu:
Lý thuyết đồ thị - Chương 1: Giới thiệuLý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 ...