A grafikon csúcsokból és élekből áll. A csúcsokat élek kötik össze egy bizonyos tulajdonság szerint - az incidencia relációval, amely meghatározza az élek halmazát. Ebben az esetben hurkok és elszigetelt csúcsok alakulhatnak ki.
Utasítás
1. lépés
Adjuk meg a gráf éleinek halmazát, és adjuk meg azt a relációt, amely mentén egy él csúcsáról a másikra húzható. Például az {1, 2, 3, 4, 5, 6, 7, 8} csúcsok halmaza, két x és y csúcs x + y <8 arányban vannak.
2. lépés
Készítsen egy csúcs szomszédsági mátrixot. Ehhez készítsen egy négyzet alakú táblázatot, a táblázat sorainak és oszlopainak száma egybeesik a csúcsok számával. Ezután tegyen 1-et az i-edik és a j-edik oszlop metszéspontjába, ha az i és j csúcsok megfelelnek az adott aránynak. Tedd 0-val az i-edik és a j-edik oszlop metszéspontját, ha a megfelelő elemek aránya nem teljesül.
Példánkban az első sort a következőképpen töltjük ki:
1 + 1 <8, tehát 1 van az 1. sor és az 1. oszlop metszéspontjában
1 + 2 <8, ismét 1
1 + 3 <8, ismét 1
1 + 7 <8, helytelen egyenlőtlenség, tehát a táblázat ezen eleme 0 lesz
1 + 8 <8, ismét 0
3. lépés
Az élek számának megismeréséhez számolja meg a szomszédsági mátrixban levők számát az élek megkettőzése nélkül.
A példában szimmetrikus mátrixot kaptunk, így először a mátrix főátlója fölött számoltuk (kékkel jelölt), majd a főátlón lévőket (pirossal jelölve). A bordák száma összesen 12.
4. lépés
Készítsen egy incidensek (élek) mátrixát. Ehhez rajzoljon egy táblázatot, a benne lévő sorok száma megegyezik a grafikon csúcsainak számával, az oszlopok száma pedig az élek számával. Helyezzen egységeket azokra a vonalakra, amelyeket egy él fog összekötni. A csúcsból hozzá vezető éleket hurkoknak nevezzük, és hozzáadjuk a mátrix végéhez. A hurkoknak megfelelő oszlopokban csak egy egység van, szemben a többi éllel.
5. lépés
Most rajzoljon egy grafikont. Bármilyen módon helyezze a csúcsokat a papírra, és a felépített táblázatokkal kösse össze élekkel. Azokat a csúcsokat, amelyeket nem kötnek össze élek, elszigeteltnek nevezzük.
