tailieunhanh - Bài giảng Toán rời rạc 2 - Khái niệm về đồ thị

Bài giảng "Toán rời rạc 2 - Khái niệm về đồ thị" cung cấp cho người học các kiến thức: Định nghĩa đồ thị, một số thuật ngữ cơ bản trên đồ thị vô hướng, một số thuật ngữ cơ bản trên đồ thị có hướng, một số dạng đồ thị đặc biệt. Mời các bạn cùng tham khảo. | Bài giảng Toán rời rạc 2 - Khái niệm về đồ thị KHÁI NIỆM VỀ ĐỒ THỊ Toán rời rạc 2 Nội dung Định nghĩa đồ thị Một số thuật ngữ cơ bản trên đồ thị vô hướng Một số thuật ngữ cơ bản trên đồ thị có hướng Một số dạng đồ thị đặc biệt Bài tập 2 Định nghĩa đồ thị Đơn đồ thị vô hướng Đơn đồ thị vô hướng G lt V E gt bao gồm V là tập các đỉnh E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. 4 Đa đồ thị vô hướng Đa đồ thị vô hướng G bao gồm V là tập các đỉnh E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. e1 E e2 E được gọi là cạnh bội nếu chúng cùng tương ứng với một cặp đỉnh. 5 Giả đồ thị vô hướng Giả đồ thị vô hướng G bao gồm V là tập đỉnh E là họ các cặp không có thứ tự gồm hai phần tử hai phần tử không nhất thiết phải khác nhau trong V được gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e u u trong đó u là đỉnh nào đó thuộc V. 6 Đơn đồ thị có hướng Đơn đồ thị có hướng G bao gồm V là tập các đỉnh E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung. 7 Đa đồ thị có hướng Đa đồ thị có hướng G bao gồm V là tập đỉnh E là cặp có thứ tự gồm hai phần tử của V được gọi là các cung. Hai cung e1 e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp. 8 Phân biệt các loại đồ thị Loại đồ thị Cạnh Có cạnh bội Có khuyên Đơn đồ thị vô hướng Vô hướng Không Không Đa đồ thị vô hướng Vô hướng Có Không Giả đồ thị vô hướng Vô hướng Có Có Đơn đồ thị có hướng Có hướng Không Không Đa đồ thị có hướng Có hướng Có Có 9 Quy ước Ta chủ yếu làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Khi viết đồ thị vô hướng ta hiểu là đơn đồ thị vô hướng . Khi viết đồ thị có hướng ta hiểu là đơn đồ thị có hướng . 10 Một số thuật ngữ cơ bản trên đồ thị vô hướng Bậc của đỉnh ĐN 1. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu u v là cạnh thuộc đồ thị G. Nếu e u v là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v hoặc ta nói cạnh e nối đỉnh u với đỉnh v đồng thời các đỉnh u và v .