A grafikon csúcsokból és élekből áll. A csúcsokat élek kötik össze egy bizonyos tulajdonság szerint - az esési viszony, amely meghatározza az élek halmazát. Ebben az esetben hurkok és izolált csúcsok alakulhatnak ki.
Használati útmutató
1
Adjunk egy grafikon éleinek sorozatát, és adjunk meg egy relációt, amellyel az egyik csúcs egyik oldaláról húzhat egy szélt. Például a {1, 2, 3, 4, 5, 6, 7, 8} csúcsok halmaza, a két x és y csúcs x + y <8 arányban van.
2
Készítsen egy csúcs szomszédsági mátrixot. Ehhez készítsen egy négyzet alakú táblát, a sorban és oszlopban lévő szám megegyezik a csúcsok számával. Ezután tegyen 1-et az i. És a j. Oszlop metszéspontjába, ha az i és j csúcsok megfelelnek az adott aránynak. Tegyük a 0 értéket az i. És a j. Oszlop metszéspontjába, ha a megfelelő elemek aránya nem teljesül.
Példánkban az első sor a következőképpen van kitöltve:
1 + 1 <8, tehát az 1. sor és az 1. oszlop metszéspontjában 1
1 + 2 <8, ismét 1
1 + 3 <8, ismét 1
…
1 + 7 <8, helytelen egyenlőtlenség, akkor ez a tábla elem 0 lesz
1 + 8 <8, ismét 0
3
Az élek számának meghatározásához számolja az egységek számát a szomszédsági mátrixban, miközben nem szaggatja az éleket.
A példában szimmetrikus mátrixot kaptunk, ezért először az mértékegységeket számoltuk a mátrix fõ átlója fölött (kékkel jelölve), majd a fõ átlós mértékegységeket (vörös jelöléssel). A bordák száma összesen 12.
4
Készítsen egy eseménymátrixot (él). Ehhez rajzoljon egy táblát, abban a sorok száma megegyezzen a grafikon csúcsainak számával, az oszlopok száma pedig egyenlő az élek számával. Helyezze az egységeket egy vonalba, amelyet egy széle fog összekapcsolni. A felülről felé vezető éleket hurkoknak nevezzük és hozzáadjuk a mátrix végéhez. A hurkoknak megfelelő oszlopokban csak egy egység van, a többi széltől eltérően.
5
Most rajzolj egy grafikont. A csúcsokat tetszőlegesen rendezze a papíron, és az összeállított táblák segítségével kösse össze a szélekkel. Az élekkel nem egymással összekötött csúcsokat izoláltnak nevezzük.
Figyelem!
Az ábra az átláthatóság érdekében a bordákat mutatja. Általában a bordák súlyát a bordára írják.
