Định nghĩa đồ thị

• Đồ thị G là tập hợp các đỉnh và các cạnh nối giữa các đỉnh đó.
• Kí hiệu

Các loại đồ thị

• Đơn đồ thị: giữa hai đỉnh bất kì chỉ có nhiều nhất một cạnh
• Đa đồ thị: giữa hai đỉnh bất kì có thể có nhiểu hơn một cạnh
• Đồ thị vô hướng: cạnh là bộ đỉnh không có thứ tự
• Đồ thị có hướng: cạnh là bộ đỉnh có thứ tự

Một số khái niệm trong đồ thị

Đỉnh kề nhau

• Xét trong đồ thị vô hướng, nếu tồn tại , ta nói u và v là hai đỉnh kề nhau, là cạnh nối hai đỉnh và , và là đầu mút của cạnh
• Xét trong đồ thị có hướng, nếu tồn tại , ta gọi là đỉnh bắt đầu, là đỉnh kết thúc của . đi ra từ và đi vào

Bậc

• Bậc của một đỉnh là số cạnh kề với nó, kí hiệu
  • đỉnh có bậc bằng không được gọi là đỉnh cô lập
  • đỉnh có bậc bằng 1 được gọi là đỉnh treo
• Đối với đồ thị có hướng:
  • bán bậc vào của một đỉnh là số cạnh đi vào đỉnh đó, kí hiệu
  • bán bậc ra của một đỉnh là số cạnh đi ra khỏi đỉnh đó, kí hiệu
  • bậc của đỉnh là tổng của bán bậc vào và bán bậc ra
  • đỉnh có bán bậc vào bằng 0 được gọi là đỉnh nguồn
  • đỉnh có bán bậc ra bằng 0 được gọi là đỉnh đích
• Trong đơn đồ thị, Tổng bậc của tất cả các đỉnh bằng hai lần số cạnh
• Số đỉnh bậc lẻ luôn là số chẵn

Đồ thị con

• Xét . được gọi là đồ thị con của nếu và
• Đồ thị con bao trùm là đồ thị con có tập đỉnh bằng tập đỉnh của đồ thị chứa nó

Đồ thị đẳng cấu

• và được gọi là đẳng cấu nếu tồn tại song ánh sao cho với mỗi thì
• Khi đó và là hai đồ thị đẳng cấu
• Điều kiện cần: hai đồ thị đẳng cấu sẽ:
  • cùng số cạnh
  • cùng số đỉnh
  • số đỉnh bậc là như nhau với mọi

Đường đi

• Xét
• Một đường đi từ đến là dãy với
• Đường đi đơn là đường đi không qua một đỉnh quá 1 lần
• Đường đi cơ bản: đường đi không qua một cạnh quá 1 lần
• Nếu tồn tại đường đi từ đến , ta nói đạt được từ
  • Mỗi đỉnh đều đạt được từ chính nó
• Chu trình là đường đi có điểm đầu trùng điểm cuối

Tính liên thông của đồ thị

• Một đồ thị vô hướng được gọi là liên thông nếu luôn tồn tại đường đi giữa hai đỉnh bất kì
  • Đồ thị có hướng được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị liên thông
  • Đồ thị có hướng được gọi là liên thông mạnh nếu luôn tồn tại đường đi giữa hai đỉnh bất kì
• Một thành phần liên thông là một đồ thị con liên thông, nhưng nếu bổ sung bất kì một cạnh/đỉnh khác sẽ khiến nó không liên thông nữa
• Đỉnh mà khi bỏ nó đi, làm tăng số thành phần liên thông của đồ thị, được gọi là đỉnh rẽ nhánh
• Cạnh với tính chất như trên được gọi là cầu

Một số đường đi đặc biệt

• Đường đi Euler là đường đi qua mỗi cạnh đúng một lần
• Chu trình Euler là đường đi qua mỗi cạnh đúng một lần, có đỉnh đầu trùng đỉnh cuối
• Đồ thị vô hướng có chu trình Euler khi và chỉ khi nó không có đỉnh bậc lẻ
• Đồ thị vô hướng có đường đi Euler khi và chỉ khi nó có đúng hai đỉnh bậc lẻ. Đó là điểm đầu và điểm cuối của đường đi
• Đường đi Halminton là đường đi qua mỗi đỉnh đúng một lần
• Chu trình Halminton là chu trình đi qua mỗi đỉnh đúng một lần, không tính điểm đầu trùng điểm cuối
• Đơn đồ thị vô hướng có số đỉnh có chu trình Halminton nếu bậc của mỗi đỉnh không nhỏ hơn