Graf mieszany


Graf mieszany w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Graf mieszanygraf, który w teorii grafów definiowany jest jako zbiory tworzące uporządkowaną trójkę. Pierwszy z nich zawiera wierzchołki grafu, drugi składa się z krawędzi nieskierowanych mających postać par nieuporządkowanych oraz trzeci obejmujący krawędzie skierowane czyli pary uporządkowane.

Definicja matematycznie mówi, że graf mieszany G to uporządkowana trójka G:=(V,E,A) spełniająca następujące warunki:

  1. V to zbiór wierzchołków,
  2. E jest zbiorem nieuporządkowanych par wierzchołków, nazywanych krawędziami,
  3. A to zbiór uporządkowanych par nazywanych krawędziami skierowanymi.

Graf mieszany jest połączeniem grafu nieskierowanego oraz skierowanego.

Zwykle zakłada się, że zbiory V, E, A są skończone. Wiele twierdzeń teorii grafów poprawnych dla skończonej ilości krawędzi i wierzchołków okazuje się nieprawdziwa dla grafów nieskończonych.

Na podstawie artykułu: "Graf mieszany" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy