A gráfelmélet szószedete

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. augusztus 17-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Itt összegyűjtöttük a gráfelmélet kifejezéseinek definícióit . A szótárban (ezen az oldalon) található kifejezésekre való hivatkozások dőlt betűvel vannak szedve .

# A B C D E F F G I K L M N O P R S T U V Y Z _ _ _ _ _ _ _

A

Automorfizmus –gráf önmagával való izomorfizmusa .
Az aciklikus gráf ciklusok nélküli gráf .

B

A gráfbázis a gráf csúcsok halmazának egy minimális részhalmaza, amelyből bármely gráfcsúcs elérhető.
A végtelen gráf olyan gráf, amelynek végtelen sok csúcsa és/vagy éle van.
Bigraph - lásd a kétoldali gráfot .
A blokk zsanérok nélküli gráf .
A (v, k, λ) paraméterekkel rendelkező blokktervezés egy v csúcson lévő teljes gráf λ multiplicitású lefedése k csúcson lévő teljes gráfokkal.

A

Csúcs vegyértéke – lásd a csúcsértéket .
Csúcs , csomópont - alapfogalom : olyan pont, ahol az élek és/vagy ívek konvergálhatnak/kiléphetnek. A G gráf csúcsainak halmazát V(G) jelöljük.
A csúcsfedő egy gráf csúcsainak halmaza, amelynek minden éle legalább egy csúcsra esik ebből a halmazból.
Egy él súlya egy súlyozott gráf adott éléhez rendelt érték . Általában a súly egy valós szám , amely esetben az él „ hosszaként ” értelmezhető.
A súlyozott gráf olyan gráf , amelynek minden éléhez egy bizonyos érték ( élsúly ) van hozzárendelve . Lásd a feliratozott grafikont .
A függő csúcs egy olyan csúcs , amelynek foka egyenlő 1-gyel (vagyis ). $d(v)=1$

A teljesen szétválasztott gráf egy 0 fokú szabályos gráf , azaz élek nélküli gráf .
A fa magassága a leghosszabb út a gyökértől a levélig .

G

A Hamilton-gráf olyan gráf, amelynek Hamilton-ciklusa van .
A Hamilton-görbe egy olyan egyszerű út egy gráfban, amely a gráf összes csúcsát pontosan egyszer tartalmazza.
A Hamilton-ciklus egy egyszerű ciklus egy gráfban, amely a gráf összes csúcsát pontosan egyszer tartalmazza.
A geometriai megvalósítás egy olyan ábra, amelynek csúcsai megfelelnek a gráf csúcsainak, élei - a gráf élei és az ábrán lévő élek összekötik a gráf csúcsainak megfelelő csúcsokat.
A geometriai gráf csúcsok lapos alakja - a sík pontjai és élei - néhány csúcspárt összekötő vonalak. Bármely gráfot sokféleképpen ábrázolhat.
A hipergráf csúcsok halmazának és hiperélek halmazának gyűjteménye (a csúcshalmaz n-edik euklideszi hatványának egy részhalmaza, vagyis a hiperélek tetszőleges számú csúcsot kötnek össze).
A homeomorf gráfok olyan gráfok, amelyeket egyetlen gráfból kapunk, élfelosztások sorozatával.
A lap egy síkgráfban élekkel határolt terület,amely nem tartalmaz gráfcsúcsokat és éleket. A sík külső része is arcot alkot.
A grafikon egy alapfogalom. Tartalmaz egy csúcshalmazt és egy élhalmazt , amely a csúcshalmaz derékszögű négyzetének részhalmaza (azaz minden él pontosan két csúcsot köt össze).
A g nemzetség gráfja olyan gráf, amely metszéspontok nélkül ábrázolható a g nemzetség felületén, és nem ábrázolható metszéspontok nélkül a g -1 nemzetség bármely felületén. Különösen a síkgráfok nemzetsége 0.

D

Kettős gráf . Egy A gráfotduálisnak nevezünk egy síki B gráfhoz , ha az A gráf csúcsai megfelelnek a B gráf lapjainak, és az A gráf két csúcsaakkor és csak akkor van összekötve éllel, ha a B gráf megfelelő lapjainak legalább egy közös él.
A kétrészes gráf (vagy bigráf , vagy páros gráf ) olyan gráf , amelyben a V csúcsok halmazaésoszlik, és bármely E él beesik egy csúcsra innenés egy csúcsra(vagyis -ból származó csúcsot köt össze -ból származócsúcshoz). Vagyis a grafikon helyes színezése két színnel történik. A éshalmazokategy bipartit gráf "részeinek" nevezzük. Egy kétrészes gráfot "teljesnek" nevezünk, ha bármely két csúcsaésszomszédos. Ha,akkor a teljes bipartit gráfot jelöli. $G(V,E)$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $\left|V_{1}\right|=a$ $\left|V_{2}\right|=b$ $K_{{a,b}}$
A duplán összefüggő gráf olyan összefüggő gráf , amelynek nincsenek csuklói .
A fa egy összefüggő gráf , amely nem tartalmaz ciklusokat .
A gráf átmérője az összes csúcspár csúcspontjai közötti maximális távolság. A csúcsok közötti távolság a két csúcsot összekötő útvonal legkisebb élszáma. $\mathrm {diam} (G)$
Útvonal hossza – az útvonal éleinek száma (ismétlésekkel). Ha az útvonal , akkor M hossza egyenlő k - val (jelölése ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\left|M\right|=k$
Az út hossza az út íveinek száma (vagy ívei hosszának összege, ha ez utóbbi adott). Tehát a v 1 , v 2 , …, v n út hossza n-1.
Az ív egy orientált él .
A gráfkomplementer egy gráf, amely ugyanazon a csúcshalmazon van, mint az eredeti, de a csúcsokat akkor és csak akkor köti össze él, ha az eredeti gráfban nincs él.

E

Egy irányítatlan G gráf szederje a G gráf egymáshoz érintő összefüggő részgráfjainak családja.

W

A csillaggráf egy teljes kétrészes gráf. $K_{{1,b}}$

És

Izolált csúcsnak nevezzük azt a csúcsot, amelynek foka 0 (azaz nincsenek élek vele ).
Izomorfizmus . Két gráfot izomorfnak mondunk, ha a csúcsok permutációja megegyezik. Más szóval, két gráfot izomorfnak nevezünk , ha csúcsai és élei között egy az egyhez egyezés van, amely megőrzi a szomszédosságot és az incidenciát (a gráfok csak a csúcsaik elnevezésében térnek el egymástól).
A gráfinvariáns egy gráf vagy rendezett vektorának olyan numerikus jellemzője, amely a gráf szerkezetét invariánsan jellemzi a csúcsok átszámozása tekintetében.
Az intervallumgráf olyan gráf, amelynek csúcsai egy az egyben hozzárendelhetők a valós tengely szegmenseihez oly módon, hogy két csúcs akkor és csak akkor esik egy élre , ha az ezeknek a csúcsoknak megfelelő szakaszok metszik egymást.
Az incidencia csak egy élre vagy egy ívre és egy csúcsra vonatkozó fogalom: ha csúcsok, és a az őket összekötő él, akkor a csúcs és az él incidens, és a csúcs és az él is incidens. Két csúcs (vagy két él) nem lehet incidens. A legközelebbi csúcsok (élek) jelölésére a szomszédság fogalmát használjuk . $v_{1}, v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $e$ $v_{2}$ $e$

K

A cella egyadott fokszámú csúcsoklegkisebb kerületének szabályos gráfja .
A klikk a gráfcsúcsok egy részhalmaza, amelyek egymással teljesen össze vannak kötve, vagyis egy részgráf, amely egy teljes gráf .
- A klikkszám a legnagyobb klikk csúcsainak száma (G) . Más nevek sűrűség, sűrűség.
- A maximális klikk az a klikk, amelynek a lehető legtöbb csúcsa van a gráf klikkjei között.
A kerék (jelölése W n ) egy n csúcsú (n ≥ 4) gráf, amelyet úgy alakítunk ki, hogy egyetlen csúcsot kapcsolunk az ( n -1)-ciklus összes csúcsához.
A tegez csak egy irányított gráf.
A véges gráf olyan gráf, amely véges számú csúcsot és élt tartalmaz.
Grafikonok konstruktív felsorolása - egy adott osztály gráfjainak teljes listájának beszerzése.
A gráf összefüggő komponense a gráf csúcsainak egy részhalmaza , amelynek bármely két csúcsához van út az egyikből a másikba, és nincs út ennek a részhalmaznak a csúcsától egy olyan csúcshoz, amely nem ebből a részhalmazból származik. .
A gráf erősen összefüggő összetevője , a réteg egy irányított gráf csúcsainak maximális halmaza, úgy, hogy ebből a halmazból bármely két csúcs számára van egy út az elsőtől a másodikig és a másodiktól az elsőig.
A körvonal egy zárt út egy digráfban .
A fa gyökere a fa kiválasztott csomópontja ; digráfban nulla bemeneti fokú csúcs.
A kociklus egy minimális vágás , egy minimális élkészlet, amelynek eltávolítása a gráfot szétválasztja.
A többszörös élek több élek , amelyekugyanarra a csúcspárra esnek . Multigráfokban található .
A köbös gráf egy 3-as fokú szabályos gráf, azaz olyan gráf, amelyben pontosan három él esik minden csúcsra.
a k-részes gráf egy G gráf, amelynek kromatikus száma c(G)=k
A k-kapcsolt gráf olyan összefüggő gráf , amelyben nincsvagy kevesebb csúcsok halmaza ,a rájuk eső csúcsok és élek eltávolításamegszakítja a gráf összekapcsolását. Konkrétan egy összefüggő gráf 1-kapcsolatos, a kétszeresen összefüggő gráf pedig 2-kapcsolatú. $V'$ $k-1$ $V'$

L

Az n csúcsú Laman-gráf egy olyan G gráf , amelyben egyrészt minden k esetén G bármely k csúcsottartalmazórészgráfja legfeljebb 2 k − 3 éllel rendelkezik, másodszor pedig a G gráfnak pontosan 2 n −3 éle van.

Az erdő egy irányítatlan gráf ciklusok nélkül. A fák az erdő összekapcsolhatósági összetevői .
A falevél egy facsúcs , amelynek egyetlen éle vagy bejövő íve van .
Egy csúcs lokális foka a rá eső élek száma. A hurok "2"-vel járul hozzá a csúcs fokához.

M

A Maxi-kód egy nehezen kiszámítható teljes gráfinvariáns , amelyet úgy kapunk, hogy a szomszédsági mátrix bináris értékeit egy sorba írjuk, majd a kapott bináris számot decimális alakra konvertáljuk. A maxi kód a sorok és oszlopok olyan sorrendjének felel meg, amelyben a kapott érték a lehető legnagyobb. $\mu _{max}$
A maximális egyezés a grafikonon. Egy illesztést maximálisnak nevezünk, ha bármely más illesztésnek kevesebb éle van.
A gráf útvonala csúcsok és élek váltakozó sorozata , amelyben bármely két szomszédos elem beesik . Ha , akkor az útvonal le van zárva , ellenkező esetben nyitva van . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
A digráf elérhetőségi mátrixa egy olyan mátrix, amely információt tartalmaz a digráf csúcsai közötti utak létezéséről.
A gráf beesési mátrixa egy olyan mátrix, amelynek elemértékeit a gráf megfelelő csúcsainak (függőlegesen) és éleinek (vízszintesen) előfordulása jellemzi. Irányítatlan gráf esetén egy elem 1 értéket vesz fel, ha a megfelelő csúcsa és éle incidens. Irányított gráf esetén az elem 1 értéket vesz fel, ha a beeső csúcs egy él eleje, és -1 értéket, ha a beeső csúcs egy él vége; más esetekben (beleértve a ciklusokat is) az elem értéke 0 .
A gráf szomszédsági mátrixa egy olyan mátrix, amelynek elemértékeit a gráf csúcsainak szomszédossága jellemzi. Ebben az esetben a mátrixelem értékéhez hozzárendeljük a megfelelő csúcsokat összekötő élek számát (vagyis, amelyekmindkét csúcsra esnek).
A minikód egy nehezen kiszámítható teljes gráfinvariáns , amelyet úgy kapunk, hogy a szomszédsági mátrix bináris értékeit egy sorba írjuk, majd a kapott bináris számot decimális alakra konvertáljuk. A minikód a sorok és oszlopok olyan sorrendjének felel meg, amelyben a kapott érték a lehető legkisebb. $\mu _{min}$
A gráf minimális kerete (vagy minimális súlyú kerete , minimális feszítőfája ) egy aciklikus (ciklusok nélküli) élhalmaz egy összefüggő, súlyozott és irányítatlan gráfban, amely összeköti a gráf összes csúcsát, miközben az összes gráf súlyainak összege élek benne minimális.
A v csúcs szomszédsági halmaza a v csúcsgal szomszédos csúcsok halmaza . Kijelölve . $\Gamma ^{+}(v)$
A minor gráf olyan gráf, amely az eredeti gráfból ívek eltávolításával és összehúzásával nyerhető.
A híd olyan él , amelynek eltávolítása megnövelia gráf összekapcsolt komponenseinek számát.
A multigráf olyan gráf, amelyben lehet egy olyan csúcspár, amelyet egynél több él köt össze (iránytalan), vagy kettőnél több ellentétes irányú ív.

H

Az irányított gráf olyan irányított gráf , amelyben két csúcsot legfeljebb egy ív köt össze.
- Az irányított aciklikus gráf kontúrok nélküli irányított gráf.
A független csúcshalmaz (más néven belsőleg stabil halmaz ) a G gráf olyan csúcskészlete, amelyben két csúcs nincs szomszédos (egy csúcspárt sem köti össze él).
- Egy független halmazt akkor nevezünk maximálisnak , ha nincs másik független halmaz, amelyben szerepelne. A legnagyobb független halmaz komplementerét a gráf minimális csúcsfedőjének nevezzük.
- A legnagyobb független halmaz a legnagyobb független halmaz.
A független csúcsok a gráf páronkénti nem szomszédos csúcsai. [egy]
Az elválaszthatatlan gráf egy összefüggő, nem üres gráf, artikulációs pontok nélkül. [2] .
A normált gráf ciklusok nélküli irányított gráf .

A null gráf ( üres gráf ) egy csúcs nélküli gráf .

Oh

A kerület a grafikon legkisebb ciklusának hossza
A gráfok (jelölt gráfokés) uniója egy olyan gráfamelynek csúcskészlete, élhalmaza pedig. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\kupa G_{2}$ $X_{1}\csésze X_{2}$ $U=U_{1}\pohár U_{2}$
A k rendű szomszédság egy adott v csúcstól k távolságra lévő csúcsok halmaza ; néha tágan értelmezve, mint v -től k -nál nem nagyobb távolságra elválasztott csúcsok halmazaként .
A környezet az adott csúcsokkal szomszédos csúcsok halmaza.
Egy digráf , egy irányított gráf G = (V,E) egy halmazpár, ahol V csúcsok (csomópontok), E ívek (irányított élek) halmaza. Az ív egy rendezett csúcspár (v, w), ahol a v csúcsot az ív kezdetének, w csúcsot pedig az ív végének nevezzük. Azt mondhatjuk, hogy a v → w ív a v csúcsból a w csúcsba vezet, míg a w csúcs szomszédos a v csúcsgal.
Egy (iránytalan) összekapcsolt gráf feszítőfája ( váza ) bármely olyan részgráf , amely fa . $G=(V,E)$ $S=(V,T)$
A feszítő részgráf az összes csúcsot tartalmazó részgráf.

P

Az illesztés páronként nem szomszédos élek halmaza.
A hurok olyan él, amelynek eleje és vége ugyanabban a csúcsban van.
A gráfok (jelölt gráfokés) metszéspontja egy olyan gráfamelynek csúcskészlete, élhalmaza pedig. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cap G_{2}$ $X_{1}\cap X_{2}$ $U=U_{1}\cap U_{2}$
Graph enumeration - egy adott osztályban (adott jellemzőkkel rendelkező) nem izomorf gráfok számának megszámlálása.
Perifériás csúcsnak nevezzük azt a csúcsot, amelynek excentricitása megegyezik a gráf átmérőjével.
A síkgráf egy olyan gráf, amely élek keresztezése nélkül rajzolható ( halmozott ) egy síkra. Izomorf egy síkgráfhoz, azaz metszéspontokkal rendelkező gráf, de lehetővé teszi annak síkbeli fektetését, ezértegy síkon lévő képpel eltérhet a síkgráftól . Így lehet különbség a sík gráf és a sík gráf között, ha síkon ábrázoljuk.
A síkgráf olyan geometriai gráf , amelyben nincs két élnek közös pontja, kivéve a mindkettőre eső csúcsot (nem metszik egymást). Ez egy halmozott gráf a síkon.
Az eredeti gráf részgráfja egy gráf, amely az adott gráf csúcsainak egy bizonyos részhalmazát és a rájuk eső élek egy bizonyos részhalmazát tartalmazza. (vö. szugráf .) Egy részgráf vonatkozásában az eredeti gráfot szupergráfnak nevezzük
A teljes gráf egy olyan gráf, amelyben minden csúcspárhozvan egy él, egy incidensés egy incidens(minden csúcsot egy él köt össze bármely másik csúcshoz). $v_{1}, v_{2}$ $v_{1}$ $v_{2}$
A teljes gráfinvariáns egy gráf vagy rendezett vektorának numerikus jellemzője, amelynek értékeiszükségesek és elegendőek a gráfizomorfizmus megállapításához.
A teljes bipartit gráf olyan kétrészes gráf , amelyben egy részhalmaz minden csúcsa egy éllel össze van kötve egy másik részhalmaz minden csúcsával
Egy csúcs digráfjában a -fok a csúcsba belépő ívek száma. Jelölése , , vagy . $v$ $d^{+}(v)$ $\mathrm {deg} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Egy csúcs digráfjának külső foka a csúcsból kilépő ívek száma. Jelölése , , vagy . $v$ $d^{-}(v)$ $\mathrm {deg} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
A címkézett gráf olyan gráf, amelynek csúcsaihoz vagy íveihez valamilyen címke van hozzárendelve, például természetes számok vagy valamilyen ábécé szimbólumai.
A generált részgráf az eredeti gráf éleinek halmaza által generált részgráf. Nem feltétlenül tartalmazza a gráf összes csúcsát, de ezeket a csúcsokat ugyanazok az élek kötik össze, mint a gráfban.
A gráf sorrendje a gráf csúcsainak száma. [3]
A megfelelő gráfszínezés olyan színezés , amelyben minden színosztály független halmaz. Más szóval, megfelelő színezés esetén bármely két szomszédos csúcsnak különböző színűnek kell lennie.
Gráfok szorzata - adott gráfok esetén a szorzat olyan gráf , amelynek csúcsai az eredeti gráfok csúcskészleteinek derékszögű szorzata. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\szer V_{2}$
Az egyszerű útvonal olyan útvonal , amelyben minden csúcs különbözik.
Az egyszerű gráf olyan gráf , amelynek nincs több éle vagy hurokja .
Az egyszerű út olyan út , amelynek minden csúcsa páronként különálló [4] . Más szóval, egy egyszerű út nem megy át kétszer ugyanazon a csúcson.
- Az egyszerű ciklus olyan ciklus , amely nem megy át kétszer ugyanazon a csúcson.
Az pszeudográf olyan gráf, amely hurkokat és/vagy több élt tartalmazhat.

Az üres gráf ( null gráf ) élek nélküli gráf .
Az út élek sorozata(iránytalan gráfban) és/vagy ívek sorozata (irányított gráfban), úgy, hogy az egyik ív vége (él) egy másik ív (él) eleje. Vagy csúcsok és ívek (élek) sorozata, amelyben minden elem az előzőre és a következőre esik [4] . Egy útvonal speciális eseteként is felfogható.
A digráfban szereplő út v 1 , v 2 , …, v n csúcsok sorozata , amelyekhez vannak v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n ívek . Ez az út a v 1 csúcstól kezdődik, v 2 , v 3 , …, v n-1 csúcson halad át , és a v n csúcsban ér véget.

R

A gráf sugara egy összefüggő gráf csúcsai excentricitásainak minimuma ; azt a csúcsot, ahol ezt a minimumot elérjük, központi csúcsnak nevezzük.
A gráf felosztása az eredeti gráf reprezentációja, mint csúcsok részhalmazainak halmaza bizonyos szabályok szerint.
A felosztott csúcs megegyezik a csuklóponttal és az artikulációs ponttal .
A gráf kibontása egy irányított gráf csúcsain definiált függvény.
A címkézett gráf egy olyan gráf, amelyre egy S címkék halmaza, egy f : A → S csúcscímkéző függvény és egy g : R → S ívcímkéző függvény adott. Grafikusan ezeket a függvényeket csúcsokon és íveken lévő címkékkel ábrázoljuk. A címkekészlet felosztható két nem átfedő csúcscímkék és ívcímkék részhalmazára.
A vágás olyan élek halmaza , amelyek eltávolítása a gráfot szétválasztja .
A keretgráf olyan gráf, amely egy síkban úgy rajzolható meg, hogy bármely korlátos lap négyszög, és bármely három vagy kevesebb szomszédos csúcs egy határtalan lapra esik. [5]
A gráf színezése a csúcsok halmazokra osztása (ezeket színeknek nevezzük). Ha ráadásul nincs két szomszédos csúcs, amely ugyanahhoz a halmazhoz tartozik (vagyis két szomszédos csúcs mindig különböző színű), akkor az ilyen színezést szabályosnak nevezzük.
A csúcsok közötti távolság az adott csúcsokat összekötő legrövidebb lánc hossza (az útdigráfban). Ha ilyen lánc (út) nem létezik, akkor a távolságot a végtelennel egyenlőnek tételezzük fel.
Az élfedő gráfélek halmaza úgy, hogy minden csúcs legalább egy élre esik ebből a halmazból.
Az irányítatlan gráf vonalgráfja egy gráf, amely a gráf éleinek szomszédságát reprezentálja.
Az Edge egy alapfogalom. Egy él a gráf két csúcsát köti össze .
A szabályos gráf olyan gráf, amelynekminden csúcsának foka egyenlő. A szabályosság foka egygráfinvariáns , és jelölése . Undefined szabálytalan grafikonokhoz. A szabályos gráfok számos algoritmus számára különleges kihívást jelentenek. $r(G)$ $r(G)$
- A 0 fokú szabályos gráf ( teljesen szétkapcsolt gráf , üres gráf , null gráf ) élek nélküli gráf .

C

Az önduális gráf olyan gráf, amely izomorf a duális gráfjával .
A hiperkarcsú (csillag alakú) fa olyan fa, amelynek egyetlen csúcsa 2-nél nagyobb.
Kapcsolódás . Egy gráf két csúcsa össze van kötve , ha van (egyszerű) út , amely összeköti őket .
Az összefüggő gráf olyan gráf, amelyben minden csúcs össze van kapcsolva.
A gráf szakasza olyan élek halmaza, amelyek eltávolítása a gráfot két elszigetelt részgráfra osztja, amelyek közül az egyik lehet triviális gráf.
A hálózat elvileg ugyanaz, mint a gráf , bár a hálózatokat általában gráfoknak nevezik, amelyek csúcsai bizonyos módon vannak címkézve.
- Az irányított hálózat egy irányított gráf, amely nem tartalmaz kontúrokat.
Erős kapcsolat . Egy irányított gráf két csúcsa erősen összefügg , ha van egy út az elsőből a másodikba és a másodikból az elsőbe.
- Az erősen összefüggő digráf olyan digráf , amelyben minden csúcs erősen összefügg.
Szomszédság – csak két élre vagy csak két csúcsra használt fogalom : Az egy csúcsra eső két élt szomszédosnak nevezzük ; két, ugyanarra az élre eső csúcsot szomszédosnak is nevezzük . (vö. incidens .)
A vegyes gráf olyan gráf, amely irányított és irányítatlan éleket is tartalmaz .
A tökéletes illeszkedés olyan illesztés, amely tartalmazza a gráf összes csúcsát.
Két gráf és , amelyeknek nincs közös csúcsa, összekapcsolását gráfnak nevezzük . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\pohár V_{2},E_{1}\csésze E_{2}\csésze V_{1}\times V_{2}\pohár V_{2} \times V_{1})$

A definícióból látható, hogy a gráfok összekapcsolása a kommutativitás és az asszociativitás tulajdonságaival rendelkezik

A gráf spektruma a szomszédsági mátrix összes sajátértékének halmaza, több él figyelembevételével.
A csúcs foka a G gráf azon éleinek száma, amelyek az x csúcsra. Kijelölve. A G gráf csúcsának minimális fokát jelöli. és a maximum az. $d(x)$ $\delta (G)$ $\Delta (G)$
A gráf élének összehúzódása - az él végeit egy csúcsra cseréljük, ezeknek a végeknek a szomszédai az új csúcs szomszédaivá válnak. A gráf összehúzható ,ha a második megkapható az elsőből élösszehúzódások sorozatával. $G_{1}$ $G_{2}$
Az eredeti gráf részgráfja ( részgráfja ) egy olyan gráf, amely az eredeti gráf összes csúcsát és éleinek egy részhalmazát tartalmazza . (vö. algráf .)
Szupergráf - bármely gráf, amely tartalmazza az eredeti gráfot (vagyis amelynél az eredeti gráf egy részgráf )

T

A Theta-gráf egy gráf, amely három olyan út egyesüléséből áll, amelyeknek nincs közös csúcsa, és ugyanazok a végpontjai [7]
Az euklideszi síkban lévő ponthalmaz théta-gráfja minden csúcsot körülvevő kúprendszerként van megszerkesztve, minden egyes kúp élével hozzáadva a halmaz azon pontjához, amelynek vetülete a kúp központi tengelyére minimális.

Az identitásgráf olyan gráf, amelyre csak egyetlen automorfizmus lehetséges – . Képletesen szólva, az identitásgráf egy "abszolút nem szimmetrikus" gráf.
Az artikulációs pont ugyanaz, mint a csukló és az osztócsúcs .
Felületi háromszögelés - gráf elhelyezése egy felületen , háromszög alakú területekre bontása; a topológiai háromszögelés speciális esete .
A triviális gráf olyan gráf, amelynek legfeljebb egy csúcsa van .
A verseny egy irányított gráf , amelyben minden csúcspárt egyetlen él köt össze.

Wu

A csomópont ugyanaz, mint a csúcs .
Halmozás , vagy gráfbeágyazás : a gráf valamilyen felületre halmozott, ha erre a felületre megrajzolható úgy, hogy a gráf élei nem metszik egymást. (Lásd Planar graph , Planar graph .)
A menedékhely egy bizonyos típusú függvény egy irányítatlan gráf csúcskészletein. Ha létezik fedezet, akkor a szökevény felhasználhatja azt, hogy megnyerje az üldözéses-elkerülési játékot a grafikonon úgy, hogy a játék minden lépésében ezt a funkciót használja, hogy meghatározza a biztonságos csúcshalmazokat, ahová menni kell.
A rendezett gráf olyan gráf, amelyben az egyes csúcsokból kilépő élek egyedi számozással vannak ellátva, 1-től kezdve. Az éleket növekvő számsorrendűnek tekintjük. A grafikus ábrázolás során az éleket gyakran valamilyen szabványos bejárás sorrendjében rendezettnek tekintik (például az óramutató járásával ellentétes irányba ).

F

A gráf n-tényezője egy fokozat szabályos átfeszítő részgráfja . $n$
gráf n-faktorizálása - a gráf független n-tényezőkre bontása .

X

A gráf kromatikus száma az a minimális színszám , amely a gráf csúcsainak színezéséhez szükséges úgy, hogy az éllel összekapcsolt csúcsok különböző színekkel legyenek színezve.
Egy gráf karakterisztikus polinomja a szomszédsági mátrixának karakterisztikus polinomja .

C

A gráf középpontja a csúcsok halmaza, amelyre igaz az egyenlőség:, ahol a csúcs excentricitása és a gráf sugara. $W=\left\{u_{1},u_{2},...,u_{n}\jobbra\}$ $\forall i=1,...,n:\varepszilon (u_{i})=r(G)$ $\varepsilon$ $r$
A gráfban lévő lánc olyan útvonal , amelynek minden éle különálló. Ha az összes csúcs (és így az élek) különbözőek, akkor egy ilyen láncot egyszerűnek ( elemi ) nevezünk. A láncban a és csúcsokat a lánc végeinek nevezzük . Egy u és v végű lánc köti össze az u és v csúcsokat . Az u és v csúcsokat összekötő láncot jelöli . Digráfoknál a láncot orláncnak nevezzük. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ Egyes forrásokban az egyszerű lánc olyan lánc, amelynek élei elkülönülnek, ami gyengébb állapot.
A ciklus zárt kör . Digráfoknál a ciklust körvonalnak nevezzük.
- A ciklus ( egyszerű ciklus ) egy digráfban egy legalább 1 hosszúságú egyszerű út , amely ugyanabban a csúcsban kezdődik és végződik.
- A Hamilton-ciklus megegyezik a Hamilton-ciklussal .
A gráf ciklomatikus száma az élek minimális száma, amelyet el kell távolítani ahhoz, hogy a gráf aciklikussá váljon . Összefüggő gráf esetén van egy összefüggés:ahol a ciklomatikus szám, agráf összekapcsolt összetevőinek száma, az élek száma és a csúcsok száma. $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

A parciális gráf ugyanaz, mint a szugráf .
A páros gráf ugyanaz, mint a kétrészes gráf .
Csúcsborítószám – a legkisebb csúcsfedő mérete a gráfban.
A függetlenségi szám a gráf legnagyobb független csúcskészletének mérete.
Az illesztési szám a legnagyobb egyezés mérete a grafikonon.
Élfedés száma — a legkisebb élborítás mérete a grafikonon.

W

A csukló egy gráf olyan csúcsa , amelynek eredményeként az összesrá eső éllel együtt az összefüggő komponensek száma a gráfban az eltávolítás következtében megnő.
A fogaskerék (jelölése ) egy grafikon, amelyet egy kerékből kapunk úgy, hogy további csúcsokat helyezünk el a kerület szomszédos csúcsai között . A fogaskerekek a keretgráfok családjába tartoznak, és fontos szerepet játszanak a keretgráfok tiltott részgráfjainak leírásában [8] $G_{n}$

E

Az Euler-gráf olyan gráf, amelyben van egy ciklus , amely a gráf összes élét egyszer tartalmazza (a csúcsok megismételhetők).
Euler-lánc (vagy Euler-ciklus ) - egy lánc ( ciklus ), amely tartalmazza a gráf összes élét (a csúcsok megismételhetők).
Egy csúcs excentricitása a többi csúcs és egy adott csúcs közötti minimális távolság maximuma.
Az elemi út olyan út , amelynek csúcsai az első és az utolsó kivételével eltérőek. Más szóval, egy egyszerű út nem megy át kétszer ugyanazon a csúcson, hanem kezdődhet és végződhet ugyanabban a csúcsban, ebben az esetben ciklusnak (elemi ciklusnak) nevezzük.
A következő eljárást elemi összehúzódásnak nevezzük : veszünk egy élt ( a rá eső csúcsokkal együtt , pl. u és v), és „összehúzzuk”, azaz eltávolítjuk az élt, és azonosítjuk az u és v csúcsokat. Az így kapott csúcs azokra az élekre esik (kivéve), amelyekre u vagy v eredetileg beesett.

Linkek

↑ Distel R. Gráfelmélet Per. angolról. - Novoszibirszk: Matematikai Intézet Kiadója, 2002. - 17. o.
↑ Harari F. Gráfelmélet. - M.: Mir, 1972. - S. 41.
↑ Distel R. Gráfelmélet Per. angolról. - Novoszibirszk: Matematikai Intézet Kiadója, 2002. - 16. o.
↑ 1 2 Kuznetsov O. P., Adelson-Velsky G. M. / Discrete Mathematics for an Engineer. / M .: Energia, 1980-344 p., ill. oldal 120-122
↑ A. V. Karzanov. A véges metrikák kiterjesztései és a berendezések elhelyezésének problémája // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ M. B. Abrosimov. Minimális csúcson 1-különleges alakú gráfok kapcsolatainak kiterjesztései. // Alkalmazott gráfelmélet - 2011. - Kiadás. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43-54. — (Matematikai előadásjegyzetek). - doi : 10.1007/BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Véges és végtelen négyzetgráfok kombinatorikája és geometriája // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , sz. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 . .

Irodalom

Distel R. Gráfelmélet Per. angolról. - Novoszibirszk: Matematikai Intézet Kiadója, 2002. - 336 p.
Harari F. Gráfelmélet. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .