Graf se skládá z vrcholů a hran. Vrcholy jsou spojeny hranami podle určité vlastnosti - relace dopadu, která definuje množinu hran. V tomto případě se mohou vytvořit smyčky a izolované vrcholy.
Instrukce
Krok 1
Nechť je dána množina hran grafu a je uveden vztah, podél kterého je možné nakreslit hranu z jednoho vrcholu do druhého. Jako příklad lze uvést množinu vrcholů {1, 2, 3, 4, 5, 6, 7, 8}, dva vrcholy xay jsou v poměru x + y <8.
Krok 2
Vytvořte vrcholovou matici sousedství. Chcete-li to provést, vytvořte čtvercovou tabulku, počet řádků a sloupců v tabulce se shoduje s počtem vrcholů. Poté vložte 1 na průsečík i-té řady a j-tého sloupce, pokud vrcholy i a j splňují daný poměr. Pokud není splněn poměr pro odpovídající prvky, vložte 0 na křižovatku i-tého řádku a j-tého sloupce.
V našem příkladu je první řádek vyplněn následovně:
1 + 1 <8, takže na křižovatce 1. řádku a 1. sloupce je 1
1 + 2 <8, opět 1
1 + 3 <8, opět 1
1 + 7 <8, nesprávná nerovnost, takže tento prvek tabulky bude 0
1 + 8 <8, opět 0
Krok 3
Chcete-li zjistit počet hran, spočítejte počet jedniček v matici sousedství, aniž byste hrany duplikovali.
V příkladu byla získána symetrická matice, takže jsme spočítali nejprve ty nad hlavní úhlopříčkou matice (označené modře) a potom ty na hlavní úhlopříčce (označené červenou barvou). Celkový počet žeber je 12.
Krok 4
Vytvořte matici incidentů (hran). Chcete-li to provést, nakreslete tabulku, počet řádků v ní se rovná počtu vrcholů v grafu a počet sloupců se rovná počtu hran. Umístěte jednotky na ty čáry, které budou spojeny hranou. Hrany vedoucí z vrcholu k němu se nazývají smyčky a přidávají se na konec matice. Ve sloupcích odpovídajících smyčkám je na rozdíl od ostatních okrajů pouze jedna jednotka.
Krok 5
Nyní nakreslete graf. Umístěte vrcholy na papír jakýmkoli způsobem a spojte je s hranami pomocí vytvořených tabulek. Vrcholy, které nejsou spojeny hranami, se nazývají izolované.
