- Chương 1 Kiến thức chuẩn bị về đồ thị 5. - 2.2 Lý thuyết Đồ thị. - 3.2 Các đồ thị tách. - 4.5 Số arboricity tuyến tính của đồ thị. - sở về đồ thị. - Đây là do chúng ta dùng phương pháp xác suất để giải một số bài toán liên quan dến đồ thị. - Kiến thức chuẩn bị về đồ thị. - Chúng ta nói rằng G 0 = (V 0 , E 0 ) là đồ thị con của G nếu V 0 ⊂ V và E 0 ⊂ E . - Một đồ thị con của G mà chứa mọi đỉnh của G gọi là. - đồ thị con dẫn xuất của G hay một nhân tử của G. - Nếu x là một đỉnh của đồ thị thì đôi khi chúng ta viết x ∈ G thay cho x ∈ V (G. - Chúng ta viết G n cho một đồ thị tùy ý có thứ tự n . - đồ thị con từ một đồ thị đã cho). - Theo quy ước này, nếu G và H là hai đồ thị. - Cỡ của một đồ thị thứ tự n là ít nhất 0 và nhiều nhất n 2. - có một đồ thị G(n, m. - Một đồ thị có thứ tự n với cỡ. - được gọi là n -đồ thị đầy đủ và kí hiệu bởi K n . - một n -đồ thị rỗng E n có thứ tự n và không cạnh. - Đồ thị K 1 = E 1 gọi là tầm thường.. - Một đồ thị là chính quy nếu nó là k -chính quy với k nào đó. - Một đồ thị 3 -chính quy được nói là lập phương. - đồ thị con dẫn xuất của G mà mọi đỉnh của nó có bậc 1. - Một đường là một đồ thị P có dạng. - cũng vậy, W ⊂ V (G) bao gồm các đỉnh độc lập nếu G(W ) là một đồ thị rỗng. - Có vài khái niệm liên quan đến các đường của một đồ thị. - Một di động W của một đồ thị là một dãy các đỉnh và cạnh x 0 , e 1 , x 1 , e 2. - Định lý 1.1.1 Tập các đỉnh của một đồ thị có thể phân chia thành các vòng nếu, và chỉ nếu, mọi đỉnh có bậc chẵn.. - Giả sử rằng mỗi đỉnh của đồ thị đều có bậc chẵn và e(G) >. - chúng ta có d(x 0. - Giả sử phản chứng rằng G là một đồ thị thứ tự n mà không chứa một tam giác nào. - Một đồ thị gọi là liên thông nếu mọi cặp các đỉnh phân biệt {x, y} đều có một đường từ x đến y . - Chú ý rằng một đồ thị liên thông của ít nhất hai. - Một đồ thị không chứa vòng nào là một rừng, hay một đồ thị không vòng. - nói khác đi, một rừng là một đồ thị mà mỗi thành tố của nó là một cây. - Một đồ thị G là một đồ thị hai nhánh với các lớp đỉnh V 1 , V 2 nếu V (G. - Chúng ta nhận được đồ thị nối G+ H từ G∪ H bằng cách thêm tất cả các cạnh giữa G và H . - Một siêu đồ thị là một cặp (V, E ) sao cho V ∩ E. - Chúng ta sẽ chủ yếu làm việc với các đồ thị đơn.. - Như vậy một đồ thị định hướng là một đồ thị có hướng trong đó nhiều nhất một trong hai trường hợp. - Định lý 1.2.1 Cho x là một đỉnh của đồ thị G và gọi W là một thành tố của đồ thị G mà chứa x . - Định lý 1.2.2 Một đồ thị là hai nhánh nếu và chỉ nếu nó không chứa một vòng lẻ.. - Do một đồ thị là hai nhánh nếu và chỉ nếu mỗi thành tố của nó cũng vậy, chúng ta có thể giả sử rằng G là liên thông. - Định lý 1.2.3 Một đồ thị là một rừng nếu và chỉ nếu cho mỗi cặp {x, y} của hai. - Cho G là đồ thị có nhiều nhất một đường với mỗi cặp hai. - x l là một vòng trong đồ thị G , thì x 1 x 2. - y k x l là hai đường x 0 − x l phân biệt của đồ thị G . - Định lý 1.2.4 Các khẳng định sau là tương đương cho một đồ thị G . - (b) G là một đồ thị liên thông nhỏ nhất, đó là, G là liên thông và nếu xy ∈ E(G. - đồ thị G − xy không thể chứa một đường x − y , gọi là xz 1 z 2. - và có là đồ thị liên thông nhỏ nhất. - Tiếp theo giả sử G là một đồ thị liên thông nhỏ nhất. - Cuối cùng, giả sử rằng G là đồ thị không vòng lớn nhất. - Lấy một đồ thị con liên thông nhỏ nhất chứa mọi đỉnh của. - đồ thị.. - Có vài cách dựng đơn giản một cây dẫn xuất của một đồ thị liên thông G . - Đặt T là đồ thị con của G với tập. - chúng ta có V i 6. - Cụ thể, một đồ thị thứ tự n là một cây nếu và chỉ nếu nó là liên thông và có cỡ n − 1. - tìm một đồ thị con liên thông dẫn xuất T = (V, E 0 ) của G để. - Chúng ta gọi đồ thị con liên thông dẫn xuất T như thế là một đồ thị con dẫn xuất kinh tế. - Để giải bài toán trên bằng phương pháp đồ thị, đặt G là một đồ thị mà tập các. - đồ thị con dẫn xuất liên thông nhỏ nhất.. - Thế thì T 1 = (V (G), E 0 ) là đồ thị con không vòng lớn nhất của G , theo Định lý 1.2.4(c) thì T 1 chính là một cây dẫn xuất của G. - Một vòng chứa tất cả các đỉnh của đồ thị gọi là một vòng Hamilton của đồ thị.. - Một đường Hamilton của đồ thị là một đường chứa tất cả các đỉnh của đồ thị, Một đồ thị chứa một vòng Hamilton gọi là Hamiltonian.. - Một đồ thị là Eulerian nếu nó có một chu trình Euler. - Định lý 1.3.2 Một đồ thị liên thông không tầm thường có một chu trình Euler nếu và chỉ nếu mọi đỉnh của nó có bậc chẵn. - Gọi G là một đồ thị liên thông không tầm thường trong đó mọi đỉnh đều có bậc chẵn. - Phương pháp xác suất là một công cụ mạnh và hiệu quả của lý thuyết Đồ thị và Tổ hợp. - Định lý 2.2.2 Cho G = (V, E ) là đồ thị n đỉnh, bậc nhỏ nhất δ >. - Một siêu đồ thị là một cặp H = (V, E. - Gọi m(n) là số cạnh nhỏ nhất có thể của siêu đồ thị n -đều mà không có tính chất B. - Gọi H = (V, E ) là một siêu đồ thị n -đều với ít hơn 2 n−1 cạnh. - Định lý 3.2.1 Cho G = (V, E ) là một đồ thị có n đỉnh và e cạnh. - G chứa một đồ thị hai nhánh với ít nhất e/2 cạnh.. - Định lý 3.2.2 Nếu G là một đồ thị có 2n đỉnh và e cạnh thì nó chứa một đồ thị hai nhánh với ít nhất 2n−1 en cạnh. - Một đồ thị có hướng D = (V, E ) trên tập các đỉnh V = {1, 2. - n} được gọi là đồ thị có hướng phụ thuộc vào các sự kiện A 1 , A 2. - Nếu khác, theo giả thiết có một đồ thị có hướng D = (V, E) phụ thuộc vào các sự kiện A 1 , A 2. - Cho mỗi tập S của k đỉnh của K n , gọi A S là sự kiện rằng đồ thị đầy đủ trên S là. - 2 , do ít nhất thì các đồ thị đầy. - và bậc ngoài lớn nhất d trong đồ thị có hướng phụ thuộc là. - Tương tự, cho mỗi tập k đỉnh S , gọi B S là sự kiện đồ thị đầy đủ trên S màu. - Xác định một siêu đồ thị vô hạn H = (V (H. - của mọi đồ thị d -chính quy là d(d + 1)/2e. - Cũng chú ý rằng mỗi đồ thị G với bậc lớn nhất ∆ là một đồ thị con của một đồ thị. - Giả thuyết 4.5.2 Cho mọi đồ thị có hướng d -chính quy D , dla (D. - Mệnh đề 4.5.3 Cho H = (V, E) là một đồ thị với bậc lớn nhất d , và cho V = V 1 ∪ V 2. - Định lý 4.5.4 Cho G = (U, F ) là một đồ thị có hướng d -chính quy, chu vi có hướng g ≥ 8ed . - Như đã biết, F có thể phân hoạch thành d đồ thị con dẫn xuất. - Bổ đề 4.5.5 Cho G = (V, E) là một đồ thị có hướng d -chính quy, và p là một số nguyên thỏa mãn 10. - Do đó, có một đồ thị có hướng phụ thuộc vào tất cả các sự kiện của chúng ta ở trên với bậc lớn nhất ≤ (2d) 2 .p . - Gọi G = (V, E ) là một đồ thị có hướng d -chính quy tùy ý. - p , gọi G i = (V, E i ) là đồ thị con có hướng dẫn xuất của G xác định bởi E i = {(u, v. - 0 sao cho với mọi đồ thị có hướng d -chính quy G. - 0 sao cho với mọi đồ thị vô hướng d -chính quy G. - Chúng ta xác định một đồ thị có hướng đối xứng G trên tập đỉnh T bằng cách tạo (i, j, i 0 , j 0 ) kề với (p, q, p 0 , q 0 ) nếu và chỉ nếu {i, i 0. - đúng là bốn thì đồ thị kết quả là liên thông. - Trình bày cơ sở về đồ thị.