Glosář teorie grafů

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. srpna 2022; kontroly vyžadují 2 úpravy .

Zde jsou shromážděné definice pojmů z teorie grafů . Odkazy na termíny v tomto slovníku (na této stránce) jsou uvedeny kurzívou .

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

A

Automorfismus – Izomorfismus grafu se sebou samým.
Acyklický graf je graf bez cyklů .

B

Základ grafu je minimální podmnožina množiny vrcholů grafu, ze které je dosažitelný jakýkoli vrchol grafu.
Nekonečný graf je graf, který má nekonečně mnoho vrcholů a/nebo hran.
Bigraph - viz bipartitní graf .
Blok je graf bez pantů .
Blokový návrh s parametry (v, k, λ) je pokrytí s násobností λ kompletního grafu na v vrcholech úplnými grafy na k vrcholech.

V

Valence vrcholu - viz stupeň vrcholu .
Vrchol , uzel – základní koncept : bod , kde se hrany a/nebo oblouky mohou sbíhat/vystupovat. Množinu vrcholů grafu G označíme V(G).
Vrcholový kryt je množina vrcholů v grafu tak, že každá hrana dopadá na alespoň jeden vrchol z této množiny.
Váha hrany je hodnota přiřazená dané hraně váženého grafu . Váha je obvykle reálné číslo , v takovém případě ji lze interpretovat jako „ délku “ hrany.
Vážený graf je graf , jehož každé hraně je přiřazena určitá hodnota ( váha hrany ). Viz označený graf .
Visící vrchol je vrchol , jehož stupeň je roven 1 (tj. ). $d(v)=1$

Zcela nesouvislý graf je pravidelný graf stupně 0, tedy graf bez hran .
Výška stromu je nejdelší cesta od kořene k listu .

G

Hamiltonovský graf je graf, který má hamiltonovský cyklus .
Hamiltonovská cesta je jednoduchá cesta v grafu, která obsahuje všechny vrcholy grafu právě jednou.
Hamiltonovský cyklus je jednoduchý cyklus v grafu obsahující všechny vrcholy grafu právě jednou.
Geometrická realizace je obrazec, jehož vrcholy odpovídají vrcholům grafu, hrany - okraje grafu a hrany na obrázku spojují vrcholy odpovídající vrcholům v grafu.
Geometrický graf je plochý obrazec vrcholů - bodů roviny a hran - přímek spojujících některé dvojice vrcholů. Může reprezentovat libovolný graf mnoha způsoby.
Hypergraf je soubor množiny vrcholů a množiny hyperhran (podmnožina n-té euklidovské mocniny množiny vrcholů, tj. hyperhrany spojují libovolný počet vrcholů).
Homeomorfní grafy jsou grafy získané z jednoho grafu pomocí sekvence hranových poddělení.
Plocha je oblast ohraničená hranami v rovinném grafu a neobsahuje vrcholy a hrany grafu. Vnější část roviny tvoří také obličej.
Graf je základní pojem. Zahrnuje sadu vrcholů a sadu hran , která je podmnožinou kartézského čtverce množiny vrcholů (to znamená, že každá hrana spojuje přesně dva vrcholy).
Graf rodu g je graf, který lze zobrazit bez průsečíků na ploše rodu g a nelze jej zobrazit bez průsečíků na žádné ploše rodu g -1. Zejména rovinné grafy mají rod 0.

D

Duální graf . Graf A se nazývá duální k rovinnému grafu B , jestliže vrcholy grafu A odpovídají plochám grafu B a dva vrcholy grafu A jsou spojeny hranou právě tehdy, když odpovídající plochy grafu B mají alespoň jednu společný okraj.
Bipartitní graf (nebo bigraf , nebo sudý graf ) je graftakový, že množina vrcholů V je rozdělena na dvě neprotínající se podmnožinya, a jakákoli hrana E je incidentní s vrcholem oda vrchol od(tj. spojuje vrchol ods vrcholem od). To znamená, že správné vybarvení grafu se provádí dvěma barvami. Množinyase nazývají „části“ bipartitního grafu. Bipartitní graf se nazývá „úplný“, pokud jsou jakékoli dva vrcholy vasousedí. Jestliže,, pak je úplný bipartitní graf označen. $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}}$
Dvojitě souvislý graf je souvislý graf , který nemá žádné panty .
Strom je souvislý graf , který neobsahuje cykly .
Průměr grafu je maximální vzdálenost mezi vrcholy pro všechny páry vrcholů. Vzdálenost mezi vrcholy je nejmenší počet hran na cestě spojující dva vrcholy. $\mathrm {diam} (G)$
Délka trasy - počet hran v trase (s opakováním). Pokud je trasa , pak je délka M rovna k (označeno ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\left|M\right|=k$
Délka cesty je počet oblouků cesty (nebo součet délek jejích oblouků, pokud jsou zadány). Takže pro cestu v 1 , v 2 , …, v n je délka n-1.
Oblouk je orientovaná hrana .
Doplněk grafu je graf nad stejnou sadou vrcholů jako původní, ale vrcholy jsou spojeny hranou právě tehdy, když v původním grafu žádná hrana není.

E

Ostružina neorientovaného grafu G je rodina spojených podgrafů grafu G , které jsou navzájem tečné.

W

Hvězdný graf je úplný bipartitní graf. $K_{{1,b}}$

A

Izolovaný vrchol je vrchol, jehož stupeň je 0 (to znamená, že s ním nejsou žádné hrany ) .
Izomorfismus . O dvou grafech se říká , že jsou izomorfní , pokud existuje permutace vrcholů taková, že jsou stejné. Jinými slovy, dva grafy se nazývají izomorfní , pokud mezi jejich vrcholy a hranami existuje korespondence jedna ku jedné, která zachovává sousedství a incidenci (grafy se liší pouze jmény svých vrcholů).
Invariant grafu je numerická charakteristika grafu nebo jejich uspořádaného vektoru, která charakterizuje strukturu grafu invariantně s ohledem na přečíslování vrcholů.
Intervalový graf je graf, jehož vrcholy lze přiřadit jedna k jedné segmentům na reálné ose tak, že dva vrcholy jsou incidentní se stejnou hranou právě tehdy, když se segmenty odpovídající těmto vrcholům protínají.
Incident je koncept používaný pouze ve vztahu k hraně nebo oblouku a vrcholu: pokud jsou vrcholy a a je hrana je spojující, pak jsou vrchol a hrana incidentní a vrchol a hrana jsou také incidentní. Dva vrcholy (nebo dvě hrany) nemohou být incidentní. K označení nejbližších vrcholů (hran) se používá pojem sousedství . $v_{1},v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $E$ $v_{2}$ $E$

K

Buňka je pravidelný graf nejmenšího obvodu pro daný stupeň vrcholů.
Klika je podmnožina vrcholů grafu, které jsou vzájemně zcela propojeny, tedy podgraf, který je úplným grafem .
- Číslo kliky je počet (G) vrcholů největší kliky. Další názvy jsou hustota, hustota.
- Maximální klika je klika s maximálním možným počtem vrcholů mezi klikami grafu.
Kolo (označené W n ) je graf s n vrcholy (n ≥ 4) vytvořený spojením jediného vrcholu se všemi vrcholy ( n -1)-cyklu.
Toulec je jen orientovaný graf.
Konečný graf je graf obsahující konečný počet vrcholů a hran.
Konstruktivní výčet grafů - získání kompletního seznamu grafů v dané třídě.
Souvislá složka grafu je podmnožinou vrcholů grafu , pro kterékoli dva vrcholy existuje cesta z jednoho do druhého a neexistuje žádná cesta z vrcholu této podmnožiny k vrcholu, který není z této podmnožiny .
Silně propojená složka grafu , vrstva je maximální množina vrcholů orientovaného grafu , taková, že pro libovolné dva vrcholy z této množiny existuje cesta jak z prvního do druhého, tak z druhého do prvního.
Obrys je uzavřená cesta v digrafu .
Kořen stromu je vybraný uzel stromu ; v digrafu vrchol s nulovým stupněm vstupu.
Kocyklus je minimální řez , minimální sada hran, jejichž odstraněním se graf rozpojí.
Více hran je více hran , které dopadají na stejnou dvojici vrcholů. Nalezeno v multigrafech .
Krychlový graf je pravidelný graf stupně 3, tedy graf, ve kterém ke každému vrcholu dopadají právě tři hrany.
k-partitní graf je graf G, jehož chromatické číslo c(G)=k
K-souvislý graf je souvislý graf , ve kterém neexistuje žádná množinanebo méněvrcholů, takže odstranění všech vrcholů a hran , které k nim přiléhají , přeruší spojitost grafu. Konkrétně souvislý graf je 1-souvislý a dvojitě spojený graf je 2-souvislý. $PROTI'$ $k-1$ $PROTI'$

L

Lamanův graf s n vrcholy je graf G takový, že za prvé pro každé k má každý podgraf G obsahující k vrcholů nejvýše 2 k − 3 hran a za druhé graf G má právě 2 n −3 hran.

Les je neorientovaný graf bez cyklů. Stromy jsou prvky konektivity lesa .
List stromu je vrchol stromu s jednou hranou nebo přicházejícím obloukem .
Lokální stupeň vrcholu je počet hran, které k němu přiléhají. Smyčka přispívá "2" ke stupni vrcholu.

M

Maxi-kód je těžko vypočítatelný kompletní grafový invariant získaný zapsáním binárních hodnot matice sousednosti do řádku a následným převedením výsledného binárního čísla do desítkové formy. Maxikód odpovídá takovému pořadí řádků a sloupců, ve kterém je výsledná hodnota maximální možná. $\mu _{max}$
Maximální shoda v grafu. Shoda se nazývá maximální, pokud má jakákoli jiná shoda méně hran.
Trasa v grafu je střídající se posloupnost vrcholů a hran , ve kterých jsou jakékoli dva sousední prvky incidentní . Pokud , pak je trasa uzavřena , jinak je otevřená . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
Matice dosažitelnosti digrafu je matice obsahující informace o existenci cest mezi vrcholy v digrafu.
Incidenční matice grafu je matice, jejíž hodnoty prvků jsou charakterizovány výskytem odpovídajících vrcholů grafu (vertikálně) a jeho hran (horizontálně). U neorientovaného grafu nabývá prvek hodnotu 1 , pokud jsou jeho odpovídající vrchol a hrana incidentní. Pro orientovaný graf nabývá prvek hodnotu 1 , pokud je dopadající vrchol začátkem hrany, hodnotu -1 , pokud je dopadající vrchol koncem hrany; v ostatních případech (včetně cyklů for ) je hodnota prvku přiřazena 0 .
Matice přilehlosti grafu je matice, jejíž hodnoty prvků jsou charakterizovány přilehlostí vrcholů grafu. V tomto případě je hodnotě maticového prvku přiřazen počet hran, které spojují odpovídající vrcholy (tj. které jsou incidentní s oběma vrcholy).
Minikód je těžko vypočítatelný úplný grafový invariant získaný zapsáním binárních hodnot matice sousednosti do řádku a následným převedením výsledného binárního čísla do desítkové formy. Minikód odpovídá takovému pořadí řádků a sloupců, ve kterém je výsledná hodnota co nejmenší. $\mu _{min}$
Minimální rámec (neboli rámec minimální váhy , minimální kostra ) grafu je acyklická (bez cyklů) množina hran v spojeném, váženém a neorientovaném grafu spojující všechny vrcholy tohoto grafu, přičemž součet vah všech hrany v něm jsou minimální.
Množina sousedství vrcholu v je množina vrcholů sousedících s vrcholem v . Určeno . $\Gamma ^{+}(v)$
Menší graf je graf, který lze získat z původního grafu odstraněním a stažením oblouků.
Most je hrana , jejíž odstraněním se zvýší počet připojených komponent v grafu.
Multigraf je graf, ve kterém může být dvojice vrcholů, které jsou spojeny více než jednou hranou (neorientované), nebo více než dvěma oblouky opačných směrů.

H

Orientovaný graf je orientovaný graf , ve kterém jsou dva vrcholy spojeny nejvýše jedním obloukem.
- Orientovaný acyklický graf je orientovaný graf bez vrstevnic .
Nezávislá množina vrcholů (také známá jako vnitřně stabilní množina ) je množina vrcholů grafu G, ve kterém žádné dva vrcholy nesousedí (žádný pár vrcholů není spojen hranou).
- Nezávislá množina se nazývá maximální , když neexistuje žádná jiná nezávislá množina, do které by byla zahrnuta. Doplněk největší nezávislé množiny se nazývá minimální vrcholové krytí grafu.
- Největší nezávislá množina je největší nezávislá množina.
Nezávislé vrcholy jsou po párech nesousedící vrcholy grafu. [jeden]
Neoddělitelný graf je souvislý, neprázdný graf bez artikulačních bodů. [2] .
Normovaný graf je orientovaný graf bez cyklů .

Nulový graf ( prázdný graf ) je graf bez vrcholů .

Oh

Obvod je délka nejmenšího cyklu v grafu.
Sjednocení grafů (označené grafya) je grafjehož množina vrcholů je, a množina hran je. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cup G_{2}$ $X_{1}\pohár X_{2}$ $U=U_{1}\pohár U_{2}$
Okolí řádu k je množina vrcholů ve vzdálenosti k od daného vrcholu v ; někdy interpretován široce jako soubor vrcholů oddělených od v ve vzdálenosti ne větší než k .
Prostředí je množina vrcholů sousedících s daným.
Digraf , orientovaný graf G = (V,E) je dvojice množin, kde V je množina vrcholů (uzlů), E je množina oblouků (směrovaných hran). Oblouk je uspořádaná dvojice vrcholů (v, w), kde vrchol v se nazývá začátek a w je konec oblouku. Můžeme říci, že oblouk v → w vede z vrcholu v do vrcholu w, zatímco vrchol w sousedí s vrcholem v.
Kostra ( kostra ) (neorientovaného) souvislého grafu je jakýkoli částečný graf , který je stromem . $G=(V,E)$ $S=(V,T)$
Překlenovací podgraf je podgraf obsahující všechny vrcholy.

P

Shoda je množina po párech nesousedících hran.
Smyčka je hrana, jejíž začátek a konec jsou ve stejném vrcholu.
Průsečík grafů (označené grafya) je grafjehož množina vrcholů je, a množina hran je. $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}$
Výčet grafů - sčítání počtu neizomorfních grafů v dané třídě (s danými vlastnostmi).
Periferní vrchol je vrchol, jehož excentricita se rovná průměru grafu.
Rovinný graf je graf, který lze nakreslit ( naskládat ) na rovinu bez křížení hran. Je izomorfní k rovinnému grafu, to znamená, že je to graf s průsečíky, ale umožňuje jeho rovinné pokládání, proto se od rovinného grafu může lišit obrazem v rovině. Může tedy existovat rozdíl mezi rovinným grafem a rovinným grafem při zobrazení v rovině.
Rovinný graf je geometrický graf , ve kterém žádné dvě hrany nemají společné body, kromě vrcholu spadajícího do obou z nich (neprotínají se). Je to skládaný graf na rovině.
Podgraf původního grafu je graf obsahující určitou podmnožinu vrcholů daného grafu a určitou podmnožinu hran k nim přiléhajících . (srov . sugraph .) S ohledem na podgraf se původní graf nazývá supergraf
Úplný graf je graf, ve kterém pro každou dvojici vrcholůexistuje hrana, incidenta incident(každý vrchol je spojen hranou s jakýmkoli jiným vrcholem). $v_{1},v_{2}$ $v_{1}$ $v_{2}$
Úplný invariant grafu je numerická charakteristika grafu nebo jejich uspořádaného vektoru, jehož hodnoty jsou nezbytné a dostatečné pro stanovení izomorfismu grafu
Kompletní bipartitní graf je bipartitní graf , ve kterém je každý vrchol jedné podmnožiny spojen hranou s každým vrcholem jiné podmnožiny.
V -stupeň v digrafu pro vrchol je počet oblouků vstupujících do vrcholu. Označeno , , nebo . $proti$ $d^{+}(v)$ $\mathrm {deg} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Outdegree v digrafu pro vrchol je počet oblouků vycházejících z vrcholu. Označeno , , nebo . $proti$ $d^{-}(v)$ $\mathrm {deg} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
Označený graf je graf, jehož vrcholům nebo obloukům je přiřazen nějaký druh označení, například přirozená čísla nebo symboly nějaké abecedy.
Generovaný podgraf je podgraf generovaný sadou hran v původním grafu. Nemusí nutně obsahovat všechny vrcholy grafu, ale tyto vrcholy jsou spojeny stejnými hranami jako v grafu.
Pořadí grafu je počet vrcholů grafu. [3]
Správné zbarvení grafu je takové zbarvení , že každá třída barev je nezávislou množinou. Jinými slovy, při správném vybarvení musí mít jakékoli dva sousední vrcholy různé barvy.
Součin grafů - pro dané grafy je součinem graf , jehož vrcholy jsou kartézským součinem množin vrcholů původních grafů. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\krát V_{2}$
Jednoduchá cesta je cesta , ve které jsou všechny vrcholy odlišné.
Jednoduchý graf je graf , který nemá více hran nebo smyček .
Jednoduchá cesta je cesta , jejíž vrcholy jsou po párech odlišné [4] . Jinými slovy, jednoduchá cesta neprochází stejným vrcholem dvakrát.
- Jednoduchý cyklus je cyklus , který neprochází stejným vrcholem dvakrát.
Pseudograf je graf, který může obsahovat smyčky a/nebo více hran.

Prázdný graf ( nulový graf ) je graf bez hran .
Cesta je posloupnost hran (v neorientovaném grafu) a/nebo oblouků (v orientovaném grafu), takže konec jednoho oblouku (hrana) je začátkem dalšího oblouku (hrana). Nebo posloupnost vrcholů a oblouků (hran), ve kterých je každý prvek incidentní s předchozím a následujícím [4] . Lze si to představit jako zvláštní případ trasy .
Cesta v digrafu je posloupnost vrcholů v 1 , v 2 , …, v n , pro které existují oblouky v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Říká se, že tato cesta začíná ve vrcholu v 1 , prochází vrcholy v 2 , v 3 , …, v n-1 a končí ve vrcholu v n .

R

Poloměr grafu je minimem excentricit vrcholů spojeného grafu; vrchol, při kterém je tohoto minima dosaženo, se nazývá centrální vrchol.
Rozdělení grafu je zobrazením původního grafu jako množiny podmnožin vrcholů podle určitých pravidel.
Rozdělený vrchol je stejný jako kloubový a kloubový bod .
Rozbalení grafu je funkce definovaná na vrcholech orientovaného grafu.
Označený graf je graf, pro který je dána množina označení S, funkce označování vrcholů f : A → S a funkce označování oblouku g : R → S. Graficky jsou tyto funkce reprezentovány popisky na vrcholech a obloucích. Sadu štítků lze rozdělit na dvě nepřekrývající se podmnožiny štítků vrcholů a štítků oblouků.
Řez je množina hran , jejichž odstraněním se graf rozpojí .
Rámcový graf je graf, který lze nakreslit v rovině tak, že jakákoliv ohraničená plocha je čtyřúhelník a každý vrchol se třemi nebo méně sousedy dopadá na neohraničenou plochu. [5]
Barvení grafu je rozdělení vrcholů do množin (tzv. barvy). Pokud navíc neexistují dva sousední vrcholy patřící do stejné množiny (tedy dva sousední vrcholy mají vždy různé barvy), pak se takové zbarvení nazývá pravidelné.
Vzdálenost mezi vrcholy je délka nejkratšího řetězce (v digrafu cesty) spojujícího dané vrcholy. Pokud takový řetězec (cesta) neexistuje, předpokládá se, že vzdálenost je rovna nekonečnu.
Pokrytí hran je množina hran grafu tak, že každý vrchol dopadá na alespoň jednu hranu z této množiny.
Spojnicový graf neorientovaného grafu je graf představující okolí hran grafu.
Edge je základní koncept. Hrana spojuje dva vrcholy grafu.
Regulární graf je graf, jehož stupně všech vrcholů jsou stejné. Stupeň pravidelnosti jegraf invariantní a označuje se . Nedefinováno pro nepravidelné grafy. Pravidelné grafy představují zvláštní výzvu pro mnoho algoritmů. $r(G)$ $r(G)$
- Regulární graf stupně 0 ( zcela rozpojený graf , prázdný graf , nulový graf ) je graf bez hran .

C

Samoduální graf je graf, který je izomorfní ke svému duálnímu grafu .
Hyperštíhlý (hvězdovitý) strom je strom, který má jeden vrchol stupně větší než 2.
Konektivita . Dva vrcholy v grafu jsou spojeny , pokud je spojuje (jednoduchá) cesta .
Souvislý graf je graf, ve kterém jsou spojeny všechny vrcholy.
Úsek grafu je množina hran, jejichž odstranění rozděluje graf na dva izolované podgrafy, z nichž jeden může být triviálním grafem.
Síť je v principu to samé jako graf , i když sítě se obvykle nazývají grafy, jejichž vrcholy jsou označeny určitým způsobem.
- Orientovaná síť je orientovaný graf, který neobsahuje vrstevnice.
Silná konektivita . Dva vrcholy v orientovaném grafu jsou silně propojené , pokud existuje cesta od prvního k druhému a od druhého k prvnímu.
- Silně spojený digraf je digraf , ve kterém jsou všechny vrcholy pevně spojeny.
Přilehlost – pojem používaný ve vztahu pouze ke dvěma hranám nebo pouze dvěma vrcholům : Dvě hrany spadající do jednoho vrcholu se nazývají sousední ; dva vrcholy spadající do stejné hrany se také nazývají sousední . (viz Incident .)
Smíšený graf je graf, který obsahuje řízené i neorientované hrany .
Dokonalá shoda je shoda, která obsahuje všechny vrcholy grafu.
Spojení dvou grafů a , které nemají společné vrcholy, se nazývá graf . [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}\pohár E_{2}\pohár V_{1}\krát V_{2}\pohár V_{2} \times V_{1})$

Z definice je vidět, že spojení grafů má vlastnosti komutativnosti a asociativnosti

Spektrum grafu je množina všech vlastních hodnot matice sousedství, přičemž se bere v úvahu více hran.
Stupeň vrcholu je počet hran grafu G , které dopadají na vrchol x . Určeno. Minimální stupeň vrcholu grafu G značíme. a maximum je. $d(x)$ $\delta (G)$ $\Delta (G)$
Kontrakce hrany grafu - nahrazení konců hrany jedním vrcholem, sousedé těchto konců se stanou sousedy nového vrcholu. Graf je kontrahovatelný ,pokud lze druhý získat z prvního pomocí sekvence hranových kontrakcí. $G_{1}$ $G_{2}$
Podgraf ( částečný graf ) původního grafu je graf obsahující všechny vrcholy původního grafu a podmnožinu jeho hran . (viz pododstavec .)
Supergraph - jakýkoli graf obsahující původní graf (to znamená, pro který je původní graf podgrafem )

T

Theta-graf je graf sestávající ze spojení tří cest, které nemají společné vrcholy uvnitř a mají stejné koncové vrcholy [7]
Theta graf množiny bodů v euklidovské rovině je konstruován jako systém kuželů obklopujících každý vrchol s hranou pro každý kužel přidanou k bodu množiny, jehož projekce na centrální osu kužele je minimální.

Identitní graf je graf, pro který je možný pouze jeden automorfismus – graf identity . Obrazně řečeno, graf identity je „absolutně nesymetrický“ graf.
Kloubový bod je stejný jako kloub a dělicí vrchol .
Triangulace povrchu - položení grafu na povrch a jeho rozdělení na trojúhelníkové oblasti; speciální případ topologické triangulace .
Triviální graf je graf, který má nejvýše jeden vrchol .
Turnaj je orientovaný graf , ve kterém je každá dvojice vrcholů spojena jednou hranou.

Wu

Uzel je stejný jako Vertex .
Stohování , neboli vkládání grafu : graf je naskládán na nějakou plochu, pokud jej lze na tuto plochu nakreslit tak, aby se okraje grafu neprotínaly. (Viz Rovinný graf , Rovinný graf .)
Úkryt je určitý typ funkce na množinách vrcholů neorientovaného grafu. Pokud existuje krytí, může jej uprchlík použít k vítězství ve hře na honěnou-vyhýbání se na grafu pomocí této funkce v každém kroku hry k určení bezpečných sad vrcholů, do kterých má jít.
Uspořádaný graf je graf, ve kterém jsou hrany vycházející z každého vrcholu jednoznačně očíslovány od 1. Hrany jsou považovány za seřazené ve vzestupném pořadí čísel. V grafickém znázornění jsou hrany často považovány za uspořádané v pořadí nějakého standardního průchodu (například proti směru hodinových ručiček ).

F

N-faktor grafu je pravidelný podgraf stupně . $n$
n-faktorizace grafu - rozdělení grafu na nezávislé n-faktory .

X

Barevné číslo grafu je minimální počet barev potřebný k obarvení vrcholů grafu tak, aby všechny vrcholy spojené hranou byly obarveny různými barvami.
Charakteristický polynom grafu je charakteristický polynom jeho matice sousednosti .

C

Střed grafu je množina vrcholů, pro které platí rovnost:, kde je excentricita vrcholu a je poloměr grafu. $W=\left\{u_{1},u_{2},...,u_{n}\right\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
Řetězec v grafu je trasa , jejíž všechny hrany jsou odlišné. Pokud jsou všechny vrcholy (a tím i hrany) různé, pak se takový řetězec nazývá jednoduchý ( elementární ). V řetězci se vrcholy a nazývají konce řetězce. Řetězec s konci u a v spojuje vrcholy u a v . Řetězec spojující vrcholy u a v označíme . U digrafů se řetěz nazývá orchain. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ V některých zdrojích je jednoduchý řetěz řetěz, jehož okraje jsou zřetelné, což je slabší stav.
Cyklus je uzavřený okruh . U digrafů se cyklus nazývá obrys .
- Cyklus ( jednoduchý cyklus ) v digrafu je jednoduchá cesta o délce alespoň 1, která začíná a končí ve stejném vrcholu.
- Hamiltonův cyklus je stejný jako Hamiltonův cyklus .
Cyklomatické číslo grafu je minimální počet hran, které musí být odstraněny, aby byl graf acyklický . Pro souvislý graf platí vztah:kde je cyklomatické číslo, je počet spojených složek grafu, je počet hran a je počet vrcholů . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

Částečný graf je stejný jako sugraph .
Sudý graf je stejný jako bipartitní graf .
Číslo pokrytí vrcholu — velikost nejmenšího pokrytí vrcholu v grafu.
Číslo nezávislosti je velikost největší nezávislé množiny vrcholů v grafu.
Shodné číslo je velikost největší shody v grafu.
Číslo krytí hran — velikost nejmenšího krytí hran v grafu.

W

Pant je vrchol grafu , v důsledku čehož se spolu se všemi hranami , které k němupřiléhají, v důsledku jeho odstranění zvětšujepočet spojených komponent v grafu.
Ozubené kolo (označené ) je graf získaný z kola umístěním dalších vrcholů mezi každou dvojici sousedních vrcholů obvodu . Gears patří do rodiny rámových grafů a hrají důležitou roli v popisu zakázaných podgrafů rámových grafů [8] $G_{n}$

E

Eulerův graf je graf, ve kterém existuje cyklus obsahující všechny hrany grafu jednou (vrcholy se mohou opakovat).
Eulerův řetězec (nebo Eulerův cyklus ) - řetězec ( cyklus ), který obsahuje všechny hrany grafu (vrcholy se mohou opakovat).
Excentricita vrcholu je maximum ze všech minimálních vzdáleností od ostatních vrcholů k danému vrcholu.
Elementární cesta je cesta , jejíž vrcholy, snad s výjimkou prvního a posledního, jsou různé. Jinými slovy, jednoduchá cesta neprochází stejným vrcholem dvakrát, ale může začínat a končit ve stejném vrcholu, v takovém případě se nazývá cyklus (elementární cyklus).
Následující postup se nazývá elementární kontrakce : vezmeme hranu (společně s vrcholy , které k ní spadají , například u a v) a „stáhneme“ ji, to znamená, že odstraníme hranu a identifikujeme vrcholy u a v. Takto získaný vrchol je incidentní s těmi hranami (jinými než), ke kterým u nebo v původně dopadalo.

Odkazy

↑ Distel R. Teorie grafů Per. z angličtiny. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - S. 17.
↑ Harari F. Teorie grafů. - M.: Mir, 1972. - S. 41.
↑ Distel R. Teorie grafů Per. z angličtiny. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - S. 16.
↑ 1 2 Kuzněcov O. P., Adelson-Velsky G. M. / Diskrétní matematika pro inženýra. / M .: Energie, 1980-344 s., ill. Strana 120-122
↑ A. V. Karzanov. Rozšíření konečných metrik a problém umístění zařízení // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ M. B. Abrosimov. Na minimálním vrcholu 1-rozšíření spojení grafů speciálního tvaru. // Aplikovaná teorie grafů - 2011. - Vydání. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43-54. — (Poznámky z matematiky). - doi : 10.1007/BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Kombinatorika a geometrie konečných a nekonečných čtvercových grafů // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , no. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 . .

Literatura

Distel R. Teorie grafů Per. z angličtiny. - Novosibirsk: Nakladatelství Ústavu matematiky, 2002. - 336 s.
Harari F. Teorie grafů. — M .: URSS , 2003. — 300 s. — ISBN 5-354-00301-6 .