Sousednosti Grafu

< Zpět | Další | Obsah >

Sousednosti: Vrchol k Vrcholu

graf rodiny tvrdí, že jedním z nejlepších způsobů, jak reprezentovat je do matice, je tím, počítání počtu hran mezi dvěma sousedními vrcholy.

o dvou vrcholech se říká, že sousedí nebo sousedí, pokud podporují alespoň jednu společnou hranu.

začněme příkladem

graf níže má tři vrcholy. Takto vytvoříme sousedící matici velikosti 3 x 3. Pak položíme název vrcholů na stranu matice. Podívejte se na obrázek a začneme prázdnou maticí. Pouze názvy vrcholů jsou tam

vyplnit sousednosti, jsme se podívat na název vrcholu v řádku a sloupci. Pokud jsou tyto vrcholy spojeny hranou nebo více, počítáme počet hran a vložíme toto číslo jako maticový prvek.

Vrchol vrchol má jeden společný okraj, můžeme říci, že Vrchol vrchol jsou sousední (soused). Jsme zadání čísla hrany v matici buněk, které odpovídají vertex vrchol .

Vrchol je v blízkosti jednoho okraje. Zadáme tedy počet hran v maticové buňce, které odpovídají Vertexu .

Podobně, vertex je spojen jednou hranou. Proto jsme zadání čísla hrany v matici buněk, které odpovídají vertex

Neexistuje žádné jiné hrany grafu, tak jsme dali zbytek nevyplněné buňky v matici jako nula.

matice reprezentovat graf v tento způsob se nazývá matice Sousednosti .

velikost matice sousedství se rovná počtu vrcholů v grafu. Jedná se o čtvercovou matici (to znamená, že počet řádků se rovná počtu sloupců).

matice sousedství grafu je symetrická, protože nemá žádný směr. Dva vrcholy sdílejí stejnou hranu, kterou lze volat od prvního k druhému nebo od druhého k prvnímu. Například, Vrchol vrchol má jednu společnou hranu, pak prvek (a, b) = 1 a prvek (b, a) = 1.

zkusme jiný příklad:

můžete vytvořit matici sousedství tohoto grafu? Zkuste to nejprve, než se podíváte na odpověď níže.

graf má 3 vrcholy, takže vytvoříme velikost matice 3 x 3. Název vrcholů jsme položili na stranu matice.

Nyní se podívejte na vrchol vrchol . Kolik hran podporují dva vrcholy? Jeden. Pak jsme dát tuto hodnotu do matice

Podívejte se na vrchol vrchol . Kolik hran tyto vrcholy podporují? Žádný. Pak jsme dali nulovou hodnotu na odpovídající buňku v matici

Next, můžete se podívat na vrchol vrchol . Kolik hran tyto vrcholy podporují? Dva. Poté vložíme matici do

protože v grafu není žádná jiná hrana, můžeme prázdnou buňku vyplnit nulami. Tak, máme odpověď.

někteří z vás se mohou zeptat na diagonální část matice, jsou tyto buňky vždy nulové? Ne, pokud zjistíte, že graf má nějakou smyčku v některých vrcholech, můžete vyplnit diagonální prvek matice sousedství číslem smyčky.

Pokud graf má nějaký vrchol, který není připojen k jakékoli jiné vrcholy, sousednosti matice odpovídají, že jeden vrchol je nulová.

proveďte nějakou praxi, abyste reprezentovali graf níže do matice sousedství.

(Viz odpověď na předchozí stránku )

Vzhledem k sousednosti, můžete čerpat zpět grafu?

Zkontrolujte příklad aplikace teorie grafů v Q-Učení Návod
< Zpět | Další | Obsah >