Graf mieszany

Przykład grafu mieszanego

Graf mieszany – w teorii grafów, graf, który zawiera zarówno krawędzie nieskierowane, jak i skierowane (nazywane łukami). Formalnie jest to trójka zbiorów $(X,U\cup V),$ przy czym $X$ jest zbiorem wierzchołków grafu, $U$ zbiorem uporządkowanych par elementów z $X$ (krawędzi skierowanych), a $V$ zbiorem nieuporządkowanych par elementów z $X$ (krawędzi nieskierowanych).

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

Za pomocą grafu mieszanego można modelować między innymi sieć ulic miasta. Krawędzie skierowane w tym modelu odpowiadają ulicom jednokierunkowym.

Terminologia

W grafie mieszanym, stopniem wierzchołka nazywa się liczbę krawędzi i łuków z nim incydentnych.

Graf mieszany nazywa się spójnym, jeśli spójny jest graf zwykły powstały z niego przez zastąpienie wszystkich łuków krawędziami nieskierowanymi.