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

1

Lý thuy t đ th ế ồ ị

Ch ng 1: Gi i thi u ươ ớ ệ

2

Ch ng 1: Gi i thi 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ý hiệu hay v w.

e = vw e

3

Ch ng 1: Gi i thi u ươ ớ ệ

 Các đỉnh: A, B, C, D

 Các cạnh: AB, AC, AD,

BD, BC

A

B

C

D

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.