Graf mieszany

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)^[1].

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^[1].

Terminologia[edytuj | edytuj kod]

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

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^[1].

Przypisy[edytuj | edytuj kod]

↑ ^a ^b ^c ^d Maciej MarekM.M. Sysło Maciej MarekM.M., ZdzisławZ. Skupień ZdzisławZ., Stosowana teoria grafów III. Grafy Eulera i Hamiltona. Zagadnienie komiwojażera, „Mathematica Applicanda”, 5 (10), 1977, s. 8, DOI: 10.14708/ma.v5i10.1254, ISSN 2299-4009 (pol.).

Linki zewnętrzne[edytuj | edytuj kod]

Eric W.E.W. Weisstein Eric W.E.W., Mixed Graph, [w:] MathWorld, Wolfram Research [dostęp 2024-04-30] (ang.).

[:0-1] Maciej MarekM.M. Sysło Maciej MarekM.M., ZdzisławZ. Skupień ZdzisławZ., Stosowana teoria grafów III. Grafy Eulera i Hamiltona. Zagadnienie komiwojażera, „Mathematica Applicanda”, 5 (10), 1977, s. 8, DOI: 10.14708/ma.v5i10.1254, ISSN 2299-4009 (pol.).

[1]