Graph theory: Basic definitions

Combinatorics, Graph theory 7 Minutes

Đây là bài thứ hai của tôi về lý thuyết đồ thị. Các bạn có thể xem bài trước ở

[1] https://nttuan.org/2023/08/13/graph01/

Với mỗi tập hợp X, ký hiệu [X]^2 là tập gồm tất cả các tập con có 2 phần tử của X.

Định nghĩa 1. Một đồ thị là một cặp G=(V,E) các tập hợp sao cho E\subset [V]^2.

Như vậy, các phần tử của E là các tập con có 2 phần tử của V. Các phần tử của V được gọi là các đỉnh của đồ thị G, các phần tử của E được gọi là các cạnh của G. Đồ thị có tập các đỉnh V được gọi là đồ thị trên V. Cách thông thường để vẽ một đồ thị là mỗi đỉnh biểu thị bởi một dấu chấm và nối hai trong các dấu chấm này bởi một đường cong nếu hai đỉnh tương ứng tạo thành một cạnh.

Trong hình trên ta có một đồ thị trên V=\{1,2,\ldots,6\} với tập cạnh E=\{\{1;2\},\{2;3\},\{6;5\},\{2;4\}\}. Khi vẽ một đồ thị ta không quan tâm các đỉnh hay cạnh được vẽ thế nào, điều quan trọng duy nhất ở đây là hai đỉnh nào được nối với nhau. Tập các đỉnh của một đồ thị G được ký hiệu bởi V(G), trong khi tập cạnh của nó được ký hiệu bởi E(G). Ta thường không phân biệt đồ thị và tập cạnh hoặc tập đỉnh của nó. Chẳng hạn, ta có thể nói đỉnh v thuộc G (thay vì v\in V(G)), một cạnh e của G,…

Số đỉnh của G được gọi là cấp của nó, ký hiệu bởi \mid G\mid. Một đồ thị G được gọi là hữu hạn nếu V(G) và E(G) là hai tập hữu hạn, vô hạn nếu V(G) hoặc E(G) là một tập vô hạn. Trong bài giảng này ta chỉ xét các đồ thị hữu hạn. Khi \mid G\mid =0 ta gọi G là đồ thị rỗng, ký hiệu \emptyset. Nếu cấp của G bằng n thì ta cũng nói G là đồ thị trên n đỉnh.

Định nghĩa 2. Cho một đồ thị G. Đỉnh v của G được gọi là đầu mút của một cạnh e của G nếu v\in e. Nếu hai đầu mút của một cạnh e là x và y thì ta nói e nối x và y, hoặc e kề với hai đỉnh x và y.

Một cạnh \{x;y\} thường được viết là xy hoặc yx.

Định nghĩa 3. Cho một đồ thị G. Hai đỉnh x và y của G được gọi là kề nhau nếu \{x;y\} là một cạnh của G. Trong trường hợp đó ta nói x và y là láng giềng của nhau.

Với mỗi đỉnh x, tập gồm tất cả các đỉnh kề với x được ký hiệu là N(x) hoặc N_G(x). Hai cạnh phân biệt e và f của G được gọi là kề nhau nếu chúng có chung một đầu mút. Nếu tất cả các đỉnh của G là đôi một kề nhau ta nói G là một đồ thị đầy đủ. Một đồ thị đầy đủ trên n đỉnh được ký hiệu bởi K_n. K_3 được gọi là tam giác. Một cặp các đỉnh hay cạnh được gọi là độc lập nếu chúng không kề nhau.

Định nghĩa 4. Cho hai đồ thị G=(V,E) và G^{\prime}=(V^{\prime},E^{\prime}). Một ánh xạ \varphi: V\to V^{\prime} được gọi đồng cấu từ G đến G^{\prime} nếu nó bảo toàn quan hệ kề giữa các đỉnh, nghĩa là \varphi (x) và \varphi (y) kề nhau mỗi khi x và y kề nhau. Nếu đồng cấu \varphi từ G đến G^{\prime} là một song ánh và \varphi^{-1} cũng là một đồng cấu, thì ta nói \varphi là một đẳng cấu hoặc G và G^{\prime} là đẳng cấu.

Ta không phân biệt các đồ thị đẳng cấu, vì thế ta thường viết G=G^{\prime} để chỉ G và G^{\prime} đẳng cấu. Trong một số trường hợp ta cũng nói G^{\prime} là một bản sao của G.

Hai đồ thị G và H trong hình dưới đây là đẳng cấu. Một đẳng cấu \varphi:V(G)\to V(H) được xác định như sau:
\varphi(1)=B,\varphi(2)=D,\varphi(3)=F,\varphi(4)=C,\varphi (5)=E,\varphi (6)=A.

Hai đồ thị G và H trong hình dưới không đẳng cấu. Vì trong G có bốn đỉnh 1,3,6,8 đôi một độc lập, nhưng trong H thì không có bốn đỉnh nào như vậy.

Cho hai đồ thị G=(V,E) và G^{\prime}=(V^{\prime},E^{\prime}). Hợp của G và G^{\prime}, ký hiệu G\cup G^{\prime}, là đồ thị (V\cup V^{\prime}, E\cup E^{\prime}). Giao của G và G^{\prime}, ký hiệu G\cap G^{\prime}, là đồ thị (V\cap V^{\prime}, E\cap E^{\prime}). Nếu V^{\prime}\subset V và E^{\prime}\subset E thì ta nói G^{\prime} là đồ thị con của G, hay G chứa G^{\prime}, ký hiệu G^{\prime}\subset G. Nếu G^{\prime}\subset G và G^{\prime} chứa tất cả các cạnh xy\in E với x,y\in V^{\prime}, thì ta nói G^{\prime} là đồ thị con cảm sinh của G, và viết G[V^{\prime}] thay cho G^{\prime}. Nếu G^{\prime}\subset G và V^{\prime}=V thì G^{\prime} được gọi là đồ thị con bao trùm của G. Khi X là một tập con của V thì ta ký hiệu G\setminus X là đồ thị có được từ G bằng cách bỏ đi mọi đỉnh thuộc X và những cạnh của G kề với nó. Nếu G là đồ thị con của G^{\prime} và G^{\prime} là đồ thị con của G thì ta viết G=G^{\prime}.

Trong hình dưới, G^{\prime} và G^{\prime\prime} là các đồ thị con của G. G^{\prime} là đồ thị con cảm sinh của G, nhưng G^{\prime\prime} thì không.

Phần bù \overline{G} của G là đồ thị trên V(G) với tập cạnh [V(G)]^2\setminus E(G).  Trong hình dưới, G là một đồ thị đẳng cấu với phần bù của nó.

Do khuôn khổ của một bài viết trên blog nên tôi không cho thêm các ví dụ và bài tập liên quan đến Toán Olympic, tôi sẽ làm việc này vào một dịp khác. Bài viết cũng là tài liệu tự đọc cho các bạn học sinh lớp 9 và lớp 10 đang theo học tại \mathbf{T}^{\prime}s\, \mathfrak{Lab}.

Unknown's avatar

Published by Nguyen Trung-Tuan

A math teacher.

Published

4 thoughts on “Graph theory: Basic definitions”

  1. Pingback: The degree of a vertex – T's Lab
  2. Pingback: Connected graph  – T's Lab
  3. Pingback: Tree – T's Lab
  4. Pingback: Ramsey numbers – T's Lab

Leave a comment