xem và cài đặt ngay bản đầy đầy đủ của tư liệu tại trên đây (308.21 KB, 26 trang ) Định nghĩa trang bị thịĐồ thị là một cấu trúc rời rộc rạc gồm các đỉnh và những cạnh (vô hướng hoặc cóhướng) nối những đỉnh đó.

Bạn đang xem: Metaheuristic là gì

Người ta phân loại đồ thị tùy thuộc vào đặc tính và sốcác cạnh nối những cặp đỉnh của thứ thị. Nhiều việc thuộc gần như lĩnh vựcrất không giống nhau có thể giải được bằng mô hình đồ thị. Ta có thể dùng trang bị thịđể giải những bài toán như câu hỏi tính số những tổ hợp không giống nhau của cácchuyến bay giữa hai tp trong một mạng mặt hàng không, hay nhằm giảibài toán đi tham quan tất cả các mặt đường phố của một thành phố làm thế nào để cho mỗiđường phố đi qua đúng một lần, hoặc câu hỏi tìm số các màu cần thiết đểtô những vùng khác nhau của một phiên bản đồ.3.1.1.1 Đồ thị vô hướngĐồ thị vô phía G là 1 trong những cặp không tồn tại thứ tự G:=(V, E), trong đó:V là tập các đỉnh hoặc nútE là tập các cặp không đồ vật tự chứa những đỉnh phân biệt, được điện thoại tư vấn là cạnh.Hai đỉnh nằm trong một cạnh được hotline là những đỉnh đầu cuối của cạnh đó.3.1.1.2 Đồ thị có hướngĐồ thị được bố trí theo hướng G là một trong những cặp tất cả thứ trường đoản cú G = (V, A), vào đó:V là tập những đỉnh hoặc nútA là tập các cặp có thứ tự chứa các đỉnh, được điện thoại tư vấn là các cạnh gồm hướnghoặc cung. Một cạnh e = (x, y) được xem là có hướng từ x tới y; x được gọilà điểm đầu/gốc với y được gọi là điểm cuối/ngọn của cạnh.3.1.1.3 Đơn đồ vật thị và đa thứ thị•Đơn thứ thị (đồ thị đơn) là thiết bị thị mà không có khuyên và không cócạnh tuy vậy song.14••Đa thiết bị thị là thứ thị nhưng không thỏa thiết bị thị đơn.Đa thiết bị thị bao gồm hướng là 1 trong những đồ thị tất cả hướng, vào đó, ví như x và y làhai đỉnh thì đồ thị được phép gồm cả nhì cung (x, y) và (y, x).• Đơn đồ thị được đặt theo hướng (hoặc Đơn đồ gia dụng thị bao gồm hướng) là một trong đồ thị cóhướng, trong đó, ví như x cùng y là hai đỉnh thì đồ gia dụng thị chỉ được phép cótối đa một trong hai cung (x, y) hoặc (y, x).4.1.2. Bậc của đỉnhĐịnh nghĩa: Bậc của đỉnh v trong vật thị G = (V,E), ký kết hiệu deg(v), là sốcác cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được xem hai lầncho bậc của nó. Đỉnh v hotline là đỉnh treo nếu như deg(v) = 1 và hotline là đỉnh côlập trường hợp deg(v) = 0.Mệnh đề: cho đồ thị G = (V,E).

Xem thêm: Các Mẹ Có Ai Xài Mỹ Phẩm 3W Clinic Collagen White Có Tốt Không ?

Lúc đó:Mỗi cạnh e = (u,v) được xem một lần vào deg(u) với một lần trongdeg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bởi hai lần sốcạnh.Hệ quả: Số đỉnh bậc lẻ của một đồ gia dụng thị là một trong những chẵn.4.1.3. Bậc của đỉnhĐịnh nghĩa: Một đồ dùng thị (vô hướng) được điện thoại tư vấn là liên thông nếu gồm đườngđi giữa hầu như cặp đỉnh riêng biệt của đồ gia dụng thị. Một thiết bị thị không liên thông làhợp của nhị hay những đồ thị nhỏ liên thông, mỗi cặp những đồ thị con nàykhông tất cả đỉnh chung. Các đồ thị nhỏ liên thông tránh nhau vì vậy được gọilà các thành phần liên thông của vật thị đã xét. Như vậy, một trang bị thị làliên thông khi và chỉ khi nó chỉ bao gồm một yếu tắc liên thông.Mệnh đề: Mọi solo đồ thị n đỉnh (n ≥ 2) tất cả tổng bậc của nhì đỉnh tuỳ ýkhông nhỏ dại hơn n đều là vật dụng thị liên thông. Trường hợp một vật thị có đúng hai đỉnhbậc lẻ thì nhì đỉnh này phải liên thông, tức là có một đường đi nối chúng.4.1.4. Đồ thị Euler cùng đồ thị HamiltonĐồ thị Euler15