Tudd Intuíció, előadás, elemi fogalmai gráfelmélet
Grafikonok és mátrixok
Let - gráfot, melynek csúcsai és. Készítünk egy négyzetes mátrix sorrendben, amelyben az elem a kereszteződésekben a sor és oszlop száma a szám, meghatározása a következő:
Ez az úgynevezett a szomszédsági mátrix a grafikon. Szomszédsági mátrix lehet kialakítani egy irányított gráf, és irányítatlan, valamint a grafikonok hurkok. A hétköznapi grafikonon van két jellemző: hiánya miatt a hurkok a fő diagonális a nullák, valamint a gráf irányítatlan, akkor a mátrix szimmetrikus a fő diagonális. Ezzel szemben, a sorrendben az egyes négyzetes mátrix álló nullák és egyesek, és amelynek a két tulajdonság megfelel egy közönséges gráf a csúcsok halmaza.
Egyéb mátrix. társított a grafikon - ez az előfordulási mátrix. A konstrukció Enumerate csúcsai egész szám 1-től, és az élek - a számok 1-től. előfordulási mátrixnak sorok és oszlopok, és annak elem egyenlő 1, ha a csomópont a száma incidens élénél egy számot, különben nulla. Ábra. 1.7 ábra egy grafikon, jelzett csúcsok és az élek, és annak szomszédsági mátrix és előfordulása.
Egy irányított gráf mátrix esetén meghatározott némileg másképpen: elem ezek 1, ha a csomópont a start oldalán, és van, ha ez a vége a borda, és ez, ha ez a csomópont, és ez az él nem az eset, hogy egymással.
súlyozott grafikonok
Gyakran előfordul, különösen akkor, ha a grafikonok modellezésére használjuk valós rendszerek, tetejükön, vagy bordák, vagy mindkettő, és mások tulajdonítják bizonyos számokat. A természet ezeket a számokat lehet a legváltozatosabb. Például, ha a gráf egy modell a vasúti hálózat, a rendelt számok, hogy a szélén jelezheti a hossza a szakasz a két állomás között, vagy a legnagyobb súllyal készítmény, amely elfogadható erre útszakasz, illetve az átlagos száma vonatok áthaladó ezen a területen a nap folyamán, és m n. Bármi legyen is a értelmében ezek a számok, van egy hagyomány, hogy hívja őket súlyokat. egy grafikon egy adott csúcsban súlyok és vagy bordák - súlyozott gráf.
izomorfizmus
Ábra. 1.8 ábra két grafikon azonos csúcsok halmaza. Amikor közelebbről megvizsgáljuk előfordulhat, hogy egyes oszlopok - a bal oldalon van egy él a jogot nincs ilyen. Ugyanakkor, ha nem figyel a nevek, a csúcsok ezek grafikonok egyértelműen rendezett azonos módon: mindegyik - egy sorozat négy csúcsot. Sok esetben a szerkezet a vizsgálat gráf nevek vagy számok csúcsok nem játszanak szerepet, és az ilyen oszlopok, amelyek közül az egyik nyert a másik átnevezésével csúcsok sokkal kényelmesebb lenne tekinthető azonos. Annak érdekében, hogy meg lehet csinálni „legálisan”, bevezeti a gráfizomorfizmus.
Definíció. Grófok és izomorfak. ha létezik olyan bijekciót a sor, hogy akkor és csak akkor, ha. Display ebben az esetben az úgynevezett izomorfizmus a grafikon a grafikonon.
Az a tény, hogy a grafikonok izomorf, és van írva, mint :.
A grafikonok ábrán látható. 1.8. izomorfizmus jelentése például, kijelző. által adott alábbi táblázat tartalmazza: