Phenquestions
A gráf egy csomópontját csúcsnak nevezzük (többes szám - csúcsok). Néha még mindig csomópontnak hívják; pontnak is nevezhetjük. A gráfban lévő hivatkozást élnek nevezzük. Néha még mindig linknek hívják; vonalnak is nevezhetjük.
Grafikon sok funkcióval
Ez az ábra egy grafikont mutat be, sok funkcióval:
A körök (lemezek) csúcsok. Bármely egyenes vagy ívelt vonal vagy hurok él.
A grafikon jellemzői
Csúcs
A csúcs egy objektum. Lehet ház; lehet személy; lehet absztrakt főnév; lehet bármilyen tárgy, amire csak gondolhatsz.
Él
Az él két csúcs közötti kapcsolat (reláció); a kapcsolat elvont lehet.
Hurok
A hurok egy él, amely összeköti a csúcsot önmagával.
Arrow Edge
Tekintsünk két emberre: Jánosra és Péterre. Ha John 100 dollárt kölcsönad Péternek, és ha John és Peter csúcsok, akkor a kölcsönzési él Peter felé mutat. Ha mindkét partner elfelejti, hogy Péter tartozik Johnnak, és Peter 100 dollárt kölcsönöz Johnnak, akkor ugyanannak az élnek a másik végén nyílhegy fog mutatni John felé. Ha Peter 75 dollárt kölcsönzött Johnnak, és nem 100 dollárt, akkor egy másik él összekapcsolná Pétert Jánossal. Ennek a második élnek a nyílhegye John felé mutat. A második esetben két él van, egy-egy nyílheggyel, amelyek ellentétes irányba mutatnak.
A csúcs, amelyre egy él mutat, az él csúcspontja. A csúcs, amelyből egy él távozik, egy farokcsúcs.
Incidens
Egy él két csúcsot köt össze. Az élről azt mondják, hogy mindkét csúcsra esik. Az élnek nem kell nyílheggyel rendelkeznie. A két csúcs az él végpontjaként ismert. Lehetséges olyan gráf, ahol egy csúcs nem tartozik egyetlen élhez sem, de ezt nem vesszük figyelembe ebben az oktatóanyagban.
Irányítatlan grafikon
Az él lehet nyíl, vagy nem. Az a gráf, ahol egyetlen él sem nyíl, irányítatlan gráf. Az éleket egyenes vonal, görbe vagy hurok ábrázolhatja.
Irányított grafikon
Az a gráf, ahol minden él egy nyíl (irány), egy irányított gráf. A nyíl élét egy nyílheggyel egyenes vonal, vagy egy nyílheggyel ellátott görbe, vagy nyílheggyel ellátott hurok képviselheti.
Az irány hiánya az irányítatlan gráf szélén azt jelenti, hogy a nem irányított gráf minden éle kétirányú.
Vertex fokozata
A csúcsra eső élek száma a csúcs mértéke. A huroknak két előfordulása van egy csúcson, ezért a hurok kétszer lesz megszámolva.
Grafikon sorrendje
A grafikon sorrendje a csúcsok száma a grafikonon.
Multigráf
A multigráf egy gráf, ahol néhány csúcspár esetében több él van. Az irányítatlan multigráf olyan grafikon, amelyben az éleknek nincsenek irányaik (nem nyilak). Az irányított multigráf az, ahol minden él egy nyíl, és egynél több nyíllal rendelkező csúcspárok esetében az egyik csúcs a nyilak farka, a másik pedig ugyanazoknak a nyilaknak a feje. Az alábbi ábra egy irányítatlan multigráfot mutat:
Több él (i.e. több él) csúcspár esetén párhuzamos éleknek is nevezzük.
Reszket
A tegez egy olyan multigráf, amely lehetővé teszi a hurkok (egy vagy több hurok). Néhány multigráf nem engedélyezi a hurkok létrehozását.
Egyszerű grafikon
Az egyszerű grafikon olyan grafikon, ahol nincs két csúcspárnak több éle. A hurok nem megengedett egy egyszerű grafikonon.
Üres grafikon
Az üres grafikon olyan gráf, amelyen nincsenek csúcsok és így nincsenek élek.
Vegyes grafikon
A vegyes grafikon olyan grafikon, ahol egyes élek nyilak, mások nem; más szavakkal: egyes élek irányokkal rendelkeznek, mások pedig nem irányítottak.
Súlyozott grafikon
Lehetséges olyan grafikon, amelyben minden élhez egy számot, súlyként ismerünk. Egyes élek száma azonos, de a számok általában különböznek. Egy ilyen gráfot súlyozott gráfnak nevezünk. Egy adott grafikon számai a problémától függően hosszúságot, költségeket (árakat) vagy valamilyen nagyságrendet képviselhetnek.
Indegree és Outdegree
A szókincs, az indegree és az outgree csak irányított gráfokra vonatkozik. A grafikon lehet vagy nem multigráf. Lehet, hogy a grafikonnak vannak hurkok, vagy nem.
A csúcshoz kapcsolódó nyílhegyek száma az adott csúcs fokszáma. Az egyetlen nyílhegyű nyílnak feje és farka van. A csúcshoz kapcsolt farok száma az adott csúcs fokszáma.
Megjegyzés: Ebben az oktatóanyagban nem foglalkozunk a csúcspár több élével rendelkező grafikonokkal, ahol a több él ellentétes irányban helyezkedik el.
Grafikon szoftveres ábrázolása
A grafikon szoftveresen ábrázolható úgy, ahogyan a diagramon megrajzolták. A grafikonokat szoftveresen matematikai mátrix (kétdimenziós tömb) is ábrázolhatja. Az egyik ilyen mátrixot szomszédsági mátrixnak nevezzük.
Adjacency Matrix
A szomszédsági mátrix négyzetmátrix. A sorok címsorai mind csúcsok, növekvő sorrendben írva. Az oszlopok címsorai továbbra is ugyanazok a csúcsok, növekvő sorrendben írva. A mátrix sorainak vagy oszlopainak számlálása 1-től kezdődik, és nem nulla, mint a tömböknél. Ha egy elemet azonosít egy mátrixban, akkor a sorszámot először az oszlopszám elé írjuk.
Irányítatlan gráf esetén a szomszédsági mátrix minden bejegyzése (elem) a két megfelelő csúcsot összekötő élek száma. Egy ciklust kétszer kell megszámolni. Irányított gráf esetén a szomszédsági mátrix minden bejegyzése vagy a sor csúcsát elhagyó és a megfelelő oszlop csúcsába belépő élek száma, vagy az oszlop csúcsát elhagyó és a megfelelő sor csúcsába belépő élek száma. A választás a programozóé. Ebben a helyzetben (mindkét esetben) egy ciklust még mindig meg kell számolni.
Megjegyzés: A grafikon diagram egy önálló adatszerkezet. A szomszédsági mátrix szintén önálló adatszerkezet.
Irányítatlan grafikon és adjacencia mátrix
A következő diagramok irányítatlan grafikont és a hozzá tartozó szomszédsági mátrixot mutatnak:
A mátrix vezető átlója a bal felső és a jobb alsó átló. Egy irányítatlan mátrix szimmetrikus a vezető átlóval. Az A sor és a C oszlop mátrix bejegyzése 1, ami azt jelenti, hogy van egy él, amely összeköti az A és a C csúcsot. A C sor és a B oszlop mátrix bejegyzése 3, vagyis 3 él köti össze a C csúcsot és a B csúcsot. A többi bejegyzést hasonlóan magyarázzák.
Egy sor bejegyzéseinek összege megadja a megfelelő csúcs éleinek számát (fok). Az A sor bejegyzéseinek összege 2, vagyis 2 él kapcsolódik az A csúcshoz. A B sor bejegyzéseinek összege 6, vagyis 6 él kapcsolódik a B csúcshoz. A többi bejegyzést hasonlóan magyarázzák.
Irányított grafikon és adjacencia mátrix
A következő ábrák egy irányított grafikont és a hozzá tartozó szomszédsági mátrixot mutatják be:
Az irányított gráf szomszédsági mátrixa nem feltétlenül szimmetrikus a vezető átlóval. Az A sor és a C oszlop mátrix bejegyzése 1, ami azt jelenti, hogy az egyik él az A csúcsból a C csúcsba távozik. A C sor és a B oszlop mátrix bejegyzése 3, vagyis 3 él távozik a C csúcsból a B csúcsba. A többi bejegyzést hasonlóan magyarázzák.
Az oszlop bejegyzéseinek összege megadja az (oszlop) csúcs indexének mértékét. Egy sor bejegyzéseinek összege adja meg a (sor) csúcs outdegree értékét. Az A oszlop bejegyzéseinek összege 1, vagyis az egyik él az A csúcsra irányul. A B sor bejegyzéseinek összege 2, vagyis 2 él távozik a B csúcsból. A többi bejegyzést hasonlóan magyarázzák.
Grafikonműveletek
Az adatszerkezet, például egy grafikon, adatértékekből vagy objektumokból áll, plusz az objektumok közötti kapcsolat, valamint az objektumok közötti műveletek (függvények). A grafikon kapcsolatait az élek jelzik. Ezt követően egy grafikonnak legalább a következő műveleteket kell végrehajtania:
szomszédos (G, x, y)
G jelentése grafikon. Ez a művelet ellenőrzi, hogy egy él összeköti-e az x és az y csúcsot. A bejegyzés értéke és helye egy mátrixban jelzi az él (és annak típusa) kapcsolatát.
szomszédok (G, x)
Ez a művelet visszaadja az összes csúcs listáját, amelyek közvetlenül kapcsolódnak az x csúcshoz. A bejegyzés értéke és helye egy mátrixban jelzi az él kapcsolatát.
remove_vertex (G, x)
Ez a művelet eltávolítja az x csúcsát a grafikonból. Ha a csúcsnak nem volt éle, akkor nincs probléma. Ha azonban a csúcsnak voltak linkjei, akkor a linkeket (éleket) is el kell távolítani. A bejegyzés értéke és helye egy mátrixban egy adott csúcs jelenlétét jelzi. Ha eltávolítunk egy csúcsot, akkor a mátrixot újra kell állítani.
add_vertex (G, x)
Ez hozzáad egy csúcsot, x-et élek hozzáadása nélkül, vagy felvált egy csúcsot, amelynek élei voltak, de eltávolították. A bejegyzés értéke és helye egy mátrixban egy adott csúcs jelenlétét jelzi. Ha csúcsot adunk hozzá, akkor a mátrixot újra kell állítani.
add_edge (G, x, y)
Ez a művelet új élt ad az x és az y csúcs közé, ha az él nem volt ott. A bejegyzés értéke és helye egy mátrixban egy adott él jelenlétét jelzi. Él hozzáadásakor a mátrixot újra kell állítani.
remove_edge (G, x, y)
Ez a művelet eltávolítaná az élt az x és az y csúcs között, ha az él ott lenne. A bejegyzés értéke és helye egy mátrixban egy adott él jelenlétét jelzi. Ha egy él eltávolításra kerül, a mátrixot újra kell állítani.
get_vertex_value (G, x)
Ez a művelet az x csúccsal társított v értéket adja vissza. Ehhez a csúcscímkékhez és azok értékeihez szükséges részhalmazokra van szükség.
set_vertex_value (G, x, v)
Ez a művelet új, v értéket ad a csúcshoz társított értékhez, x. Ehhez a csúcscímkékhez és azok értékeihez szükséges részhalmazokra van szükség.
Néhány grafikon értékeket társít az éleikhez is. Az ilyen grafikonoknak a következő további műveletekre van szükségük:
get_edge_value (G, x, y)
Ez a művelet visszaadja az élhez társított v értéket, (x, y). Ennek eléréséhez szükség van az élek és azok értékeihez tartozó részhalmazok teljesítménykészletére.
set_edge_value (G, x, y, v)
Ez a művelet új, v értéket ad az élhez társított értékhez, (x, y). Ehhez az élek és azok értékeihez szükséges részhalmazok teljesítménykészlete szükséges.
Következtetés
A grafikon élekkel összekötött csúcsok halmaza. A grafikon irányíthatatlan vagy irányítható. Az élek lehetnek iránytalanok vagy irányítottak. A hurkok jelen lehetnek vagy hiányozhatnak a grafikonból. Amit meg kell tanulnia a következő, az a készlet, a teljesítmény beállítása és a grafikonokhoz kapcsolódó multiset. Ezt követően meg kell tanulnia a különféle típusú grafikonokat, például orientált grafikont, normál grafikont, teljes grafikont, kétoldalas grafikont, bajnokságdiagramot, flow hálózati grafikont stb.
Chrys
A szerzőről
Chrysanthus Forcha
A matematika integrációjának felfedezője az első elvekből és a kapcsolódó sorozatokból. Műszaki oktatás mesterképzés, szakterülete az elektronika és a számítógépes szoftver. BSc Electronics. Számítástechnikával és telekommunikációval kapcsolatos tudással és tapasztalattal is rendelkezem. 20 000 író közül én voltam a 37. legjobb író a devarticlesnél.com. Több mint 10 éve dolgozom ezeken a területeken.
Az összes bejegyzés megtekintése
