Đa đồ thị

Trong toán học, đa đồ thị (multigraph hay pseudograph) là một đồ thị được phép có nhiều cạnh (còn gọi là cạnh song song), nghĩa là các cạnh có cùng một nút kết thúc. Do đó hai đỉnh có thể được kết nối bởi nhiều cạnh.

Một đa đồ thị với nhiều cạnh (màu đỏ) vài khuyên (màu xanh). Không phải tất cả các tác giả đều cho là đa đồ thị được có khuyên.

Đa đồ thị vô hướng

Ta có một đa đồ thị G:=(V, E) với:

  • V là một tập các đỉnh.
  • E là một đa tập các cặp đỉnh không có thứ tự, cạnh không có hướng.

Đa đồ thị có thể được dùng trong mô hình các chuyến bay bởi các hãng hàng không. Trong trường hợp này đa đồ thị sẽ là một đồ thị có hướng với những cặp cạnh có hướng song song nhau nối các thành phố để cho biết có thể bay từ vị trí này đến vị trí kia.

Một số tác giả cũng cho phép đa đồ thị có khuyên, nghĩa là có một cạnh nối một đỉnh với chính nó, trong khi những người khác gọi là pseudographs và cho rằng đa đồ thị (multigraph) là không có khuyên.

Đa đồ thị có hướng

Một đa đồ thị có hướng (multidigraph) mà độ thị được phép có nhiều cung (arc),cung có cùng một đỉnh đầu và cuối. Một đa đồ thị có hướng G:=(V,A) với

  • V là tập các đỉnh.
  • A là tập các cặp đỉnh có thứ tự, được gọi là cạnh có hướng.

Một đa đồ thị hỗn hợp G:=(V,E, A) cũng có thể được định nghĩa như đồ thị hỗn hợp.

Ngoài ra ta có một đa đồ thị có hướng G:=(V, A, s, t) với

  • V là một tập các đỉnh
  • V là một tập các cạnh
  • , gán cho mỗi cạnh đỉnh nguồn của nó
  • , gán cho mỗi cạnh đỉnh đích của nó

Chú thích


Tham khảo

  • Balakrishnan, V. K.; Graph Theory, McGraw-Hill; 1 edition (ngày 1 tháng 2 năm 1997).
  • Bollobás, Béla; Modern Graph Theory, Springer; 1st edition (ngày 12 tháng 8 năm 2002).
  • Diestel, Reinhard; Graph Theory, Springer; 2nd edition (ngày 18 tháng 2 năm 2000).
  • Gross, Jonathan L, and Yellen, Jay; Graph Theory and Its Applications, CRC Press (ngày 30 tháng 12 năm 1998).
  • Gross, Jonathan L, and Yellen, Jay; (eds); Handbook of Graph Theory. CRC (ngày 29 tháng 12 năm 2003).
  • Harary, Frank; Graph Theory, Addison Wesley Publishing Company (January 1995).
  • Zwillinger, Daniel; CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC; 31st edition (ngày 27 tháng 11 năm 2002).