Matice sousedství

Matice sousedství je jedním ze způsobů, jak reprezentovat graf jako matici.

Definice

Matice sousedství grafu s konečným počtem vrcholů (číslovaných od 1 do ) je čtvercová celočíselná matice velikosti , ve které je hodnota prvku rovna počtu hran od teho vrcholu grafu k temu vrcholu. $G$ $n$ $n$ ${\mathbf A}$ $n\krát n$ $a_{i,j}$ $i$ $j$

Někdy, zejména v případě neorientovaného grafu, se smyčka (hrana od -tého vrcholu k sobě samému) počítá jako dvě hrany, to znamená, že hodnota diagonálního prvku je v tomto případě rovna dvojnásobku počtu smyček kolem sebe. -tý vrchol . $i$ ${\displaystyle a_{i,i))$ $i$

Matice sousedství jednoduchého grafu (neobsahující smyčky nebo více hran) je binární matice a obsahuje nuly na hlavní diagonále .

Matice sousedství bipartitního grafu

Matici sousednosti bipartitního grafu , jehož části mají také vrcholy , lze zapsat v následujícím tvaru ${\mathbf A}$ $r$ $s$

\mathbf {A} ={\begin{pmatrix}\mathbf {0} _{r,r}&\mathbf {B} \\\mathbf {B} ^{T}&\mathbf {0} _ {s,s}\end{pmatrix}},

kde je matice a a jsou nulové matice. V tomto případě menší matice jednoznačně reprezentuje graf a zbývající části matice mohou být vyřazeny. někdy nazývaná matice bis-adjacency. $\mathbf {B}$ $r\times s$ ${\displaystyle \mathbf {0} _{r,r))$ $\mathbf {0} _{s,s}$ $r\times r$ $s\krát s$ $\mathbf {B}$ ${\mathbf A}$ $\mathbf {B}$

Formálně nechť je bipartitní graf s částmi a . Bikonjugovaná matice je matice 0–1, ve které tehdy a jen tehdy, když . $G=(U,V,E)$ $U=\{u_{1},\tečky ,u_{r}\}$ $V=\{v_{1},\tečky ,v_{s}\}$ $r\times s$ $\mathbf {B}$ $b_{i,j}=1$ $(u_{i},v_{j})\in E$

Pokud je bipartitní multigraf nebo vážený graf, pak prvky budou počet hran mezi vrcholy nebo váhy hran . $G$ ${\displaystyle b_{i,j))$ $(u_{i},v_{j})$

Příklady

Níže je uveden příklad neorientovaného grafu a jeho odpovídající matice sousednosti . Tento graf obsahuje smyčku kolem vrcholu 1 a v závislosti na konkrétních aplikacích lze prvek považovat za rovný jedné (jak je ukázáno níže) nebo dvěma. ${\mathbf A}$ $a_{1,1}$

Graf	Matice sousedství
	${\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix)$

$a_{i,j}$ je počet hran spojujících vrcholy a a v některých aplikacích se každá smyčka ( pro některé hrana ) počítá dvakrát. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $i$

Matice sousedství prázdného grafu bez hran se skládá ze všech nul.

Vlastnosti

Matice sousedství neorientovaného grafu je symetrická , což znamená, že má skutečné vlastní hodnoty a ortogonální základ vlastních vektorů. Soubor jeho vlastních hodnot se nazývá spektrum grafu a je hlavním předmětem studia teorie spektrálních grafů .

Dva grafy a s maticemi sousednosti a jsou izomorfní právě tehdy, když existuje permutační matice taková, že $G_{1}$ $G_{2}$ $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$

{\displaystyle \mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2))

Z toho vyplývá, že matice a jsou podobné , a proto mají stejné sady vlastních čísel, determinantů a charakteristických polynomů. Opak však není vždy pravdou - dva grafy s podobnými maticemi sousedství nemusí být izomorfní (to se stane, pokud matice není permutabilní, například matice a jsou podobné, ale odpovídající grafy nejsou izomorfní). $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Síly matice

Pokud je matice sousednosti grafu , pak má matice následující vlastnost: prvek v -tém řádku, -tém sloupci je roven počtu cest z -tého vrcholu k -tému, sestávajícího přesně z hran. ${\mathbf A}$ $G$ ${\displaystyle \mathbf {A} ^{m))$ $i$ $j$ $i$ $j$ $m$

Struktura dat

Matice sousedství a seznamy sousedství jsou hlavní datové struktury , které se používají k reprezentaci grafů v počítačových programech.

Použití matice sousednosti je výhodnější pouze v případě neřídkých grafů s velkým počtem hran, protože vyžaduje uložení jednoho bitu dat pro každý prvek. Pokud je graf řídký, pak bude většina paměti promarněna ukládáním nul, ale v případě neřídkých grafů představuje matice sousednosti graf v paměti poměrně kompaktně, s využitím asi kousku paměti, což může být řád mnohem lepší než seznamy sousedství. $n^{2}$

V algoritmech, které pracují s váženými grafy (například v algoritmu Floyd-Warshall ), prvky matice sousednosti namísto čísel 0 a 1, které označují přítomnost nebo nepřítomnost hrany, často obsahují váhy hran. oni sami. Současně se na místo chybějících hran vloží nějaká speciální hraniční hodnota ( anglicky sentinel ) , v závislosti na řešeném problému, obvykle 0 nebo . $\infty$

Viz také

Literatura

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Odkazy

Matice sousedství grafu. Programový kód v Pascalu a C++