Słowniczek teorii grafów

To jest słowniczek teorii grafów . Teoria grafów to nauka o grafach , układach węzłów lub wierzchołków połączonych parami liniami lub krawędziami .

Symbolika

Nawiasy kwadratowe [ ]: $G [S]$ to wykres podrzędny grafu $G$ dla podzbioru wierzchołków $S$ .
Symbol prim ': Symbol prim jest często używany do modyfikowania notacji dla niezmienników grafu, tak aby odnosił się do wykresu liniowego , a nie do danego wykresu. Na przykład $α (G)$ jest liczbą niezależności wykresu; $α' (G)$ jest pasującym numerem wykresu, który jest równy liczbie niezależności jego wykresu liniowego. Podobnie, $χ (G)$ jest liczbą chromatyczną wykresu; $χ'(G)$ jest indeksem chromatycznym wykresu, który jest równy liczbie chromatycznej jego wykresu liniowego.

A

absorbujący: Zbiór absorbujący $skierowanego$ to zbiór wierzchołków taki, że dla dowolnego wierzchołka $istnieje$ $setminus A$ \ } krawędź od $}$ w kierunku wierzchołka ${\ displaystyle A$ .
achromatyczny: Liczba achromatyczna wykresu to maksymalna liczba kolorów w pełnym kolorowaniu.
acykliczny: 1. Graf jest acykliczny, jeśli nie ma cykli. Nieskierowany graf acykliczny to to samo co las . Acykliczny graf skierowany, który jest digrafem bez skierowanych cykli, jest często nazywany skierowanym grafem acyklicznym , zwłaszcza w informatyce.; 2. Kolorowanie acykliczne grafu nieskierowanego to kolorowanie właściwe, w którym co dwie klasy kolorów indukują las.
macierz sąsiedztwa: Macierz sąsiedztwa grafu to macierz, której wiersze i kolumny są indeksowane przez wierzchołki grafu, z jedynką w komórce dla wiersza $i$ i kolumna $j$ , gdy wierzchołki $i$ i $j$ sąsiadują ze sobą, a zero w przeciwnym razie.
sąsiednie: 1. Relacja między dwoma wierzchołkami, które są punktami końcowymi tej samej krawędzi.; 2. Relacja między dwiema różnymi krawędziami, które mają wspólny wierzchołek końcowy.
α: W przypadku wykresu $G$ , $α (G)$ (używając greckiej litery alfa) jest jego liczbą niezależności (patrz niezależny ), a $α' (G)$ jest jego liczbą dopasowania (patrz dopasowanie ).
alterating: W grafie z dopasowaniem ścieżka naprzemienna to ścieżka, której krawędzie zmieniają się między dopasowanymi i niedopasowanymi krawędziami. Cykl naprzemienny to podobnie cykl, którego krawędzie zmieniają się między dopasowanymi i niedopasowanymi krawędziami. Ścieżka rozszerzająca to ścieżka naprzemienna, która zaczyna się i kończy w nienasyconych wierzchołkach. Większe dopasowanie można znaleźć jako różnicę symetryczną dopasowania i ścieżki rozszerzającej; dopasowanie jest maksymalne wtedy i tylko wtedy, gdy nie ma ścieżki rozszerzającej.
antyłańcuch: W skierowanym grafie acyklicznym podzbiór $S$ wierzchołków, które są nieporównywalne parami, tj. dla dowolnego $w$ $S$ $y$ ma $skierowanej$ ścieżki od do lub od $y$ do $x$ . Zainspirowany pojęciem antyłańcuchów w zbiorach częściowo uporządkowanych .
anti-edge: Synonim dla non-edge , para niesąsiadujących ze sobą wierzchołków.
antytrójkąt: Zbiór niezależny od trzech wierzchołków, dopełnienie trójkąta.
wierzchołek: 1. An graf wierzchołkowy to graf, w którym można usunąć jeden wierzchołek, pozostawiając planarny podgraf. Usunięty wierzchołek nazywamy wierzchołkiem. Graf $k$ -wierzchołkowy to graf, który można uczynić planarnym przez usunięcie $k$ wierzchołków.; 2. Synonim uniwersalnego wierzchołka , wierzchołek przylegający do wszystkich innych wierzchołków.
arborescence: Synonim drzewa zakorzenionego i ukierunkowanego; patrz drzewo .
łuk: Patrz krawędź .
arrow: Uporządkowana para wierzchołków , taka jak an krawędź w grafie skierowanym . Strzałka $(x, y)$ ma ogon $x$ , grot $y$ i kierunek $od x do y$ ; Mówimy, że $y$ $jest$ bezpośrednim następcą x $,$ a $x$ bezpośrednim poprzednikiem y . Strzałka $(y, x)$ jest odwróconą strzałką strzałki $(x, y)$ .
punkt artykulacji: Wierzchołek w połączonym grafie , którego usunięcie spowodowałoby rozłączenie grafu.
-ary: Drzewo $k$ -ary to drzewo z korzeniami, w którym każdy wewnętrzny wierzchołek ma nie więcej niż $k$ dzieci. Drzewo jednoargumentowe to tylko ścieżka. Drzewo dwuargumentowe jest również nazywane drzewem binarnym , chociaż termin ten bardziej właściwie odnosi się do drzew dwuargumentowych, w których dzieci każdego węzła są rozróżniane jako lewe lub prawe dzieci (z co najwyżej jednym dzieckiem każdego typu). Mówimy, że drzewo $k$ -ary jest kompletne, jeśli każdy wierzchołek wewnętrzny ma dokładnie $k$ dzieci.
augmenting: Specjalny rodzaj naprzemiennej ścieżki; patrz na przemian .
automorfizm: Automorfizm grafu jest symetrią grafu, izomorfizmem grafu do samego siebie.

B

worek: Jeden ze zbiorów wierzchołków w rozkładzie drzewa .
zrównoważony: Graf dwudzielny lub wielodzielny jest zrównoważony, jeśli każde dwa podzbiory jego podziału na wierzchołki mają rozmiary mieszczące się w granicach jednego od drugiego.
szerokość pasma: Szerokość pasma grafu $G$ jest minimalną, we wszystkich rzędach wierzchołków $G$ , długości najdłuższej krawędzi (liczba stopni uporządkowania między dwoma punktami końcowymi). Jest to również o jeden mniej niż rozmiar maksymalnej kliki w odpowiednim uzupełnieniu przedziału $G$ , dobranym tak, aby zminimalizować rozmiar kliki.
biclique: Synonim pełnego grafu dwudzielnego lub pełnego podgrafu dwudzielnego; zobacz kompletne .
biconnected: Zwykle synonim dla $2$ -vertex-connected , ale czasami zawiera K ₂ , chociaż nie jest 2-connected. Zobacz połączone ; dla komponentów połączonych dwustronnie , zobacz komponent .
liczba wiążąca: Najmniejszy możliwy stosunek liczby sąsiadów właściwego podzbioru wierzchołków do rozmiaru tego podzbioru.
dwudzielna: A graf dwudzielny to graf, którego wierzchołki można podzielić na dwa rozłączne zbiory w taki sposób, że wierzchołki jednego zbioru nie są ze sobą połączone, ale mogą być połączone z wierzchołkami drugiego zbioru. Innymi słowy, graf dwudzielny to graf bez nieparzystych cykli; równoważnie jest to wykres, który można odpowiednio pokolorować dwoma kolorami. Grafy dwudzielne są często zapisywane jako $G = (U, V, E)$ , gdzie $U$ i $V$ to podzbiory wierzchołków każdego koloru. Jednakże, jeśli wykres nie jest połączony, może nie mieć unikalnego 2-kolorowania.
biregularny: Graf dwuregularny to graf dwudzielny , w którym istnieją tylko dwa różne stopnie wierzchołków, po jednym dla każdego zestawu podziału na wierzchołki.
blok: 1. Blok grafu $G$ jest maksymalnym podgrafem, który jest albo izolowanym wierzchołkiem, krawędzią mostka, albo 2-spójnym podgrafem. Jeśli blok jest 2-spójny, każda para wierzchołków w nim należy do wspólnego cyklu. Każda krawędź grafu należy do dokładnie jednego bloku.; 2. Graf blokowy grafu $G$ to inny graf, którego wierzchołkami są bloki grafu $G$ , z krawędzią łączącą dwa wierzchołki, gdy odpowiednie bloki mają wspólny punkt artykulacji; to znaczy jest to wykres przecięcia bloków $G$ . Graf blokowy dowolnego grafu jest lasem .; 3. Wykres przecięcia blokowego (lub punkt przecięcia blokowego) wykresu $G$ jest grafem dwudzielnym, w którym jeden zestaw częściowy składa się z wierzchołków przecięcia $G$ , a drugi ma wierzchołek ${\ displaystyle b_ {i}}$ dla każdego bloku G. $displaystyle B_ {i}}$ ${$ \ kiedy $G$ jest spójny, jego wykres bloku-punktu przecięcia jest drzewem.; 4. Graf blokowy (nazywany również drzewem kliki, jeśli jest spójny, a czasami błędnie nazywany drzewem Husimiego) to graf, którego wszystkie bloki są grafami pełnymi. Las to graf blokowy; więc w szczególności wykres blokowy dowolnego wykresu jest wykresem blokowym, a każdy wykres blokowy może być skonstruowany jako wykres blokowy grafu.
wiązanie: Minimalny zbiór cięć : zbiór krawędzi, których usunięcie rozłącza graf, dla którego żaden właściwy podzbiór nie ma tej samej właściwości .
książka: 1. Książka , graf książkowy lub księga trójkątna to kompletny graf trójdzielny $K 1,1, n$ ; zbiór $n$ trójkątów połączonych wspólną krawędzią.; 2. Innym rodzajem grafu, zwanym też księgą lub księgą czworoboczną, jest zbiór $4$ -cykli połączonych wspólną krawędzią; iloczyn kartezjański gwiazdy z krawędzią.; 3. Osadzanie książki jest osadzeniem wykresu w księdze topologicznej, przestrzeni utworzonej przez połączenie zbioru półpłaszczyzn wzdłuż wspólnej linii. Zwykle wierzchołki osadzania muszą znajdować się na linii, która nazywa się grzbietem osadzania, a krawędzie osadzania muszą leżeć w obrębie jednej półpłaszczyzny, jednej ze stron książki.
granica: 1. W grafie osadzonym spacer po granicy to podgraf zawierający wszystkie krawędzie i wierzchołki padające na ścianę .
cierń: cierń _ jest zbiorem wzajemnie stykających się połączonych podgrafów, gdzie dwa podgrafy stykają się, jeśli mają wspólny wierzchołek lub każdy zawiera jeden punkt końcowy krawędzi. Rząd jeżyny to najmniejszy rozmiar zbioru wierzchołków, który ma niepuste przecięcie ze wszystkimi podgrafami. Szerokość drzewa grafu jest maksymalnym rzędem dowolnego z jego jeżyn.
Rozkład gałęzi: Rozkład gałęzi G to hierarchiczne skupienie krawędzi $G , reprezentowane przez nieukorzenione drzewo binarne z liśćmi$ $oznaczonymi$ krawędziami $G$ . Szerokość rozkładu gałęzi jest maksymalną, na krawędziach $e$ tego drzewa binarnego, liczby wspólnych wierzchołków między podgrafami określonymi przez krawędzie $G$ w dwóch poddrzewach oddzielonych $e$ . Szerokość gałęzi $G$ jest minimalną szerokością dowolnego rozkładu gałęzi $G$ .
branchwidth: Zobacz rozkład gałęzi .
most: 1. Most , przesmyk lub krawędź cięcia to krawędź, której usunięcie spowodowałoby rozłączenie wykresu. Graf bezmostkowy to taki, który nie ma mostków; równoważnie, wykres połączony z 2 krawędziami.; 2. Szczególnie w kontekście testowania planarności , mostek cyklu jest maksymalnym podgrafem, który jest rozłączny z cyklem i w którym każde dwie krawędzie należą do ścieżki wewnętrznie rozłącznej z cyklem. Akord to mostek z jedną krawędzią. Cykl peryferyjny to cykl z co najwyżej jednym mostkiem; musi to być ściana w dowolnym planarnym osadzeniu jej wykresu.; 3. Mostek cyklu może również oznaczać ścieżkę, która łączy dwa wierzchołki cyklu, ale jest krótsza niż którakolwiek ze ścieżek w cyklu łączących te same dwa wierzchołki. Graf mostkowany to graf, w którym każdy cykl czterech lub więcej wierzchołków ma mostek.
bezmostkowy: Graf bezmostkowy to graf, który nie ma krawędzi mostkowych; to znaczy graf o dwóch krawędziach .
motyl: 1. Graf motyla ma pięć wierzchołków i sześć krawędzi; jest utworzony przez dwa trójkąty, które mają wspólny wierzchołek.; 2. Sieć motylkowa jest grafem używanym jako architektura sieciowa w obliczeniach rozproszonych, ściśle powiązana z cyklami połączonymi sześcianami .

C

C: $C n$ jest wykresem cyklu $n$ -wierzchołków ; patrz cykl .
kaktus: Graf kaktusowy , drzewo kaktusowe, kaktusowe lub drzewo Husimi to graf spójny, w którym każda krawędź należy co najwyżej do jednego cyklu. Jego bloki to cykle lub pojedyncze krawędzie. Jeśli dodatkowo każdy wierzchołek należy do co najwyżej dwóch bloków, to jest nazywany bożonarodzeniowym kaktusem.
klatka: Klatka to graf regularny o najmniejszym możliwym rzędzie obwodu.
kanonizacja
kanoniczna: Forma kanoniczna wykresu jest niezmiennikiem takim, że dwa grafy mają równe niezmienniki wtedy i tylko wtedy, gdy są izomorficzne. Formy kanoniczne można również nazwać niezmiennikami kanonicznymi lub niezmiennikami całkowitymi i czasami są definiowane tylko dla grafów w określonej rodzinie grafów. Kanonizacja grafów to proces obliczania postaci kanonicznej.
karta: Graf utworzony z danego grafu przez usunięcie jednego wierzchołka, zwłaszcza w kontekście hipotezy rekonstrukcji . Zobacz także deck , multiset wszystkich kart wykresu.
szerokość rzeźbienia: Szerokość rzeźbienia to pojęcie szerokości wykresu analogiczne do szerokości gałęzi, ale wykorzystujące hierarchiczne skupienia wierzchołków zamiast hierarchicznych skupień krawędzi.
caterpillar: Drzewo gąsienicowe lub gąsienica to drzewo, w którym wewnętrzne węzły indukują ścieżkę.
środek: Środek grafu to zbiór wierzchołków o minimalnej mimośrodowości .
łańcuch: 1. Synonim spaceru .; 2. Przy stosowaniu metod z topologii algebraicznej do grafów, element łańcucha złożonego , czyli zbiór wierzchołków lub zbiór krawędzi.
Stała Cheegera: Zobacz rozwinięcie .
wiśnia: Wiśnia to ścieżka o trzech wierzchołkach.
χ: $χ (G)$ (używając greckiej litery chi ) to liczba chromatyczna $G$ , a $χ' (G)$ to jego indeks chromatyczny; patrz chromatyczny i kolorowanie .
dziecko: W drzewie ukorzenionym dziecko wierzchołka $v$ jest sąsiadem wierzchołka $v$ wzdłuż wychodzącej krawędzi, takiej, która jest skierowana od nasady.
akord
akord: 1. Cięciwa cyklu to krawędź, która nie należy do cyklu, dla której oba punkty końcowe należą do cyklu.; 2. Graf akordowy to graf, w którym każdy cykl czterech lub więcej wierzchołków ma akord, więc jedynymi indukowanymi cyklami są trójkąty.; 3. Graf silnie akordowy to graf akordowy, w którym każdy cykl o długości sześciu lub więcej ma akord nieparzysty.; 4. Graf akordowy dwudzielny nie jest akordowy (chyba że jest to las); jest to graf dwudzielny, w którym każdy cykl sześciu lub więcej wierzchołków ma akord, więc jedynymi indukowanymi cyklami są 4-cykle.; 5. Cięciwa koła to odcinek łączący dwa punkty na okręgu; wykres przecięcia zbioru akordów nazywany jest wykresem kołowym .
chromatyczny: Związany z kolorowaniem; patrz kolor . Teoria grafów chromatycznych to teoria kolorowania grafów. Liczba chromatyczna $χ (G)$ to minimalna liczba kolorów potrzebnych do prawidłowego pokolorowania $G$ . $χ'(G)$ to $indeks$ chromatyczny G , minimalna liczba kolorów potrzebnych do prawidłowego $zabarwienia$ krawędzi G .
wybieralna
możliwość wyboru: Graf jest $k$ -wybieralny, jeśli ma listę kolorów , gdy każdy wierzchołek ma listę $k$ dostępnych kolorów. Wybieralność wykresu to najmniejsze $k$ , dla którego jest to $k$ -do wyboru.
koło: Wykres kołowy to wykres przecięcia cięciw koła.
obwód: Obwód może odnosić się do zamkniętego szlaku lub elementu przestrzeni rowerowej ( podwykres rozpinający Eulera). Ranga obwodu grafu jest wymiarem jego przestrzeni cyklu.
obwód: Obwód wykresu to długość jego najdłuższego prostego cyklu . Graf jest hamiltonowski wtedy i tylko wtedy, gdy jego obwód jest równy jego rzędowi.
klasa: 1. klasa grafów lub rodzina grafów to (zwykle nieskończony) zbiór grafów, często określany jako grafy posiadające określone właściwości. Słowo „klasa” jest używane zamiast „zbiór”, ponieważ, o ile nie zostaną wprowadzone specjalne ograniczenia (takie jak ograniczenie rysowania wierzchołków z określonego zestawu i zdefiniowanie krawędzi jako zbiorów dwóch wierzchołków), klasy grafów zwykle nie są zbiorami po sformalizowaniu przy użyciu teorii mnogości.; 2. Klasa kolorów kolorowego wykresu to zbiór wierzchołków lub krawędzi mających jeden określony kolor.; 3. W kontekście twierdzenia Vizinga , na krawędzi kolorowania prostych wykresów, mówi się, że graf jest pierwszej klasy, jeśli jego indeks chromatyczny jest równy jego maksymalnemu stopniowi, a klasy drugiej, jeśli jego indeks chromatyczny jest równy jeden plus stopień. Zgodnie z twierdzeniem Vizinga wszystkie proste grafy należą do klasy pierwszej lub klasy drugiej.
pazur: Pazur to drzewo z jednym wierzchołkiem wewnętrznym i trzema liśćmi, czyli równoważnie pełny graf $dwudzielny K$ 1,3 . Graf bez pazurów to graf, który nie ma indukowanego podgrafu, który jest pazurem.
klika: Klika _ jest zbiorem wzajemnie przylegających wierzchołków (lub kompletnym podgrafem indukowanym przez ten zbiór). Czasami klikę definiuje się jako maksymalny zbiór sąsiadujących ze sobą wierzchołków (lub maksymalny kompletny podgraf), który nie jest częścią żadnego większego takiego zbioru (lub podgrafu). K $-$ klika to klika porządku $k$ . Numer kliki $ω (G)$ grafu $G$ jest rzędem jego największej kliki. Wykres kliki grafu G jest wykresem przecięcia maksymalnych klik w G . Zobacz także biclique , kompletny podgraf dwudzielny.
drzewo kliki: Synonim wykresu blokowego .
szerokość-kliki: Szerokość -kliki grafu $G$ to minimalna liczba odrębnych etykiet potrzebnych do skonstruowania $G$ przez operacje, które tworzą wierzchołek z etykietą, tworzą rozłączną sumę dwóch oznakowanych grafów, dodają krawędź łączącą wszystkie pary wierzchołków z danymi etykietami lub ponownie opisz wszystkie wierzchołki daną etykietą. Wykresy o szerokości kliki co najwyżej $2$ są dokładnie kografami .
zamknięte: 1. Zamknięte sąsiedztwo to takie, które obejmuje swój środkowy wierzchołek; zobacz sąsiedztwo .; 2. Zamknięty spacer to taki, który zaczyna się i kończy w tym samym wierzchołku; zobacz spacer .; 3. Graf jest domknięty przechodnio, jeśli jest równy swojemu domknięciu przechodniemu; zobacz przechodni .; 4. Właściwość wykresu jest zamknięta w przypadku niektórych operacji na wykresach, jeśli zawsze, gdy argument lub argumenty operacji mają tę właściwość, to wynik również. Na przykład właściwości dziedziczne są zamknięte pod grafami indukowanymi; właściwości monotoniczne są zamknięte pod grafami; a właściwości zamknięte dla nieletnich są zamknięte dla nieletnich.
zamknięcie: 1. Dla przechodniego domknięcia skierowanego wykresu, zobacz przechodni .; 2. Domknięcie grafu skierowanego jest zbiorem wierzchołków, które nie mają krawędzi wychodzących z wierzchołków poza domknięciem. Na przykład zlew to zamknięcie z jednym wierzchołkiem. Problem zamknięcia jest problem znalezienia zamknięcia o minimalnej lub maksymalnej wadze.
co-: Ten przedrostek ma różne znaczenia, zwykle związane z wykresami dopełniaczy . Na przykład kograf to wykres utworzony przez operacje obejmujące uzupełnianie; cocoloring klikę (jak w kolorowaniu dopełnienia).
kolorowanie
1.: Kolorowanie wykresu to oznakowanie wierzchołków grafu elementami z danego zestawu kolorów lub równoważnie podział wierzchołków na podzbiory, zwane „klasami kolorów”, z których każdy jest powiązany z jednym z kolorów.; 2. Niektórzy autorzy używają słowa „kolorystyka”, bez zastrzeżeń, na oznaczenie właściwego kolorowania, takiego, które przypisuje różne kolory punktom końcowym każdej krawędzi. W kolorowaniu grafów celem jest znalezienie odpowiedniego kolorowania, które wykorzystuje jak najmniej kolorów; na przykład grafy dwudzielne to grafy, które mają kolorowanie tylko dwoma kolorami, a twierdzenie o czterech kolorach mówi, że każdy graf planarny można pokolorować co najwyżej czterema kolorami. O grafie mówi się, że jest $k$ -kolorowy, jeśli został (właściwie) pokolorowany $k-$ kolorami i $k$ -kolorowy lub $k$ -chromatyczny, jeśli jest to możliwe.; 3. Zbadano wiele wariantów kolorowania, w tym kolorowanie krawędzi (kolorowanie krawędzi w taki sposób, aby żadne dwie krawędzie z tym samym punktem końcowym nie miały tego samego koloru), kolorowanie listy (właściwe kolorowanie z każdym wierzchołkiem ograniczone do podzbioru dostępnych kolorów), kolorowanie acykliczne (każdy dwukolorowy podgraf jest acykliczny), współkolorowanie (każda klasa kolorów indukuje niezależny zestaw lub klikę), pełne kolorowanie (co dwie klasy kolorów mają wspólną krawędź) i całkowite kolorowanie (zarówno krawędzie, jak i wierzchołki są kolorowe).; 4. Liczba kolorowania wykresu to jeden plus degeneracja . Nazywa się to tak, ponieważ zastosowanie algorytmu zachłannego kolorowania do uporządkowania degeneracyjnego grafu wykorzystuje co najwyżej tyle kolorów.
porównywalność: Graf nieskierowany jest grafem porównywalności , jeśli jego wierzchołki są elementami zbioru częściowo uporządkowanego a dwa wierzchołki sąsiadują ze sobą, gdy są porównywalne w rzędzie częściowym. Równoważnie, wykres porównywalności to wykres, który ma orientację przechodnią. Wiele innych klas grafów można zdefiniować jako grafy porównywalności specjalnych typów częściowego porządku.
dopełnienie: Wykres dopełnienia $w$ wykresu to inny wykres w tym samym zestawie wierzchołków co $G$ , z krawędzią dla każdych dwóch wierzchołków, które nie sąsiadują ze $sobą$ $G$ .
kompletny: 1. Pełny wykres to taki, w którym każde dwa wierzchołki sąsiadują ze sobą: wszystkie krawędzie, które mogłyby istnieć, są obecne. Pełny graf z $n$ wierzchołkami jest często oznaczany jako $K n$ . Kompletny graf dwudzielny to taki, w którym każde dwa wierzchołki po przeciwnych stronach podziału wierzchołków sąsiadują ze sobą. Kompletny graf dwudzielny z $wierzchołkami$ a po jednej stronie podziału i wierzchołkami $b$ po drugiej stronie jest często oznaczany jako $K a, b$ . Ta sama terminologia i notacja została również rozszerzona na kompletne grafy wielodzielne , grafy, w których wierzchołki są podzielone na więcej niż dwa podzbiory i każda para wierzchołków w różnych podzbiorach sąsiaduje ze sobą; jeśli numery wierzchołków w podzbiorach to $a, b, c, ...$ to ten graf jest oznaczony jako $K a, b, c, ...$ .; 2. Uzupełnieniem danego grafu jest supergraf, który ma pewną pożądaną właściwość. Na przykład uzupełnienie akordowe to supergraf, który jest wykresem akordowym.; 3. Kompletne dopasowanie jest synonimem idealnego dopasowania ; zobacz dopasowanie .; 4. Kolorowanie pełne to kolorowanie właściwe, w którym każdą parę kolorów wyznacza się na końcach co najmniej jednej krawędzi. Każde pokolorowanie z minimalną liczbą kolorów jest kompletne, ale mogą istnieć kompletne pokolorowania z większą liczbą kolorów. Liczba achromatyczna wykresu to maksymalna liczba kolorów w pełnym kolorowaniu.; 5. Niezmiennikiem zupełnym grafu jest synonim postaci kanonicznej, niezmiennikiem, który ma różne wartości dla grafów nieizomorficznych.
komponent: Podłączony komponent wykresu jest maksymalnie spójnym podgrafem. Termin ten jest również używany w odniesieniu do maksymalnych podgrafów lub podzbiorów wierzchołków grafu, które mają spójność wyższego rzędu, w tym komponenty dwupołączone , komponenty trójpołączone i komponenty silnie połączone .
kondensacja: Kondensacja grafu skierowanego $G$ jest skierowanym grafem acyklicznym z jednym wierzchołkiem dla każdej silnie połączonej składowej G $i$ krawędzią łączącą pary składowych, które zawierają dwa punkty końcowe co najmniej jednej krawędzi w $G$ .
stożek: Graf zawierający uniwersalny wierzchołek .
połączyć: Przyczyna połączenia .
spójny: Graf spójny to taki, w którym każda para wierzchołków tworzy punkty końcowe ścieżki. Wyższe formy łączności obejmują silną łączność w grafach skierowanych (dla każdych dwóch wierzchołków istnieją ścieżki od jednego do drugiego w obu kierunkach), grafy połączone $k -wierzchołkami$ (usunięcie mniej niż $k$ wierzchołków nie powoduje rozłączenia grafu) oraz $k$ -krawędź -połączone wykresy (usunięcie mniej niż $k$ krawędzi nie może rozłączyć wykresu).
converse: Wykres odwrotny jest synonimem wykresu transpozycyjnego; patrz transpozycja .
rdzeń: 1. $K$ -rdzeń jest podgrafem indukowanym utworzonym przez usunięcie wszystkich wierzchołków stopnia mniejszego niż $k$ oraz wszystkich wierzchołków, których stopień staje się mniejszy niż $k$ po wcześniejszych usunięciach. Zobacz degenerację .; 2. Rdzeń jest grafem $G$ takim, że każdy homomorfizm grafu z $G$ do siebie jest izomorfizmem.; 3. Rdzeniem grafu $G$ jest graf minimalny $H$ taki, że istnieją homomorfizmy od $G$ do $H$ i odwrotnie. $H$ jest unikalny aż do izomorfizmu. Można go przedstawić jako indukowany podwykres $G$ i jest rdzeniem w tym sensie, że wszystkie jego autohomomorfizmy są izomorfizmami.; 4. W teorii dopasowań grafów jądro grafu jest aspektem jego rozkładu Dulmage'a-Mendelsohna , utworzonym jako suma wszystkich maksymalnych dopasowań.
cotree: 1. Dopełnienie drzewa rozpinającego .; 2. Ukorzeniona struktura drzewiasta używana do opisu kografu , w której każdy wierzchołek kografu jest liściem drzewa, każdy wewnętrzny węzeł drzewa jest oznaczony jako 0 lub 1, a dwa wierzchołki kografu sąsiadują ze sobą wtedy i tylko wtedy, gdy ich najniższy wspólny przodek w drzewie jest oznaczony etykietą 1.
pokrycie: Pokrycie wierzchołków to zbiór wierzchołków incydentnych z każdą krawędzią grafu. Pokrycie krawędzi to zbiór krawędzi incydentnych z każdym wierzchołkiem grafu. Zbiór podgrafów grafu obejmuje ten graf, jeśli jest sumą – brane pod względem wierzchołków i krawędzi – jest równe grafowi.
krytyczny: Graf krytyczny dla danej własności to graf, który ma tę właściwość, ale taki, że żaden podgraf utworzony przez usunięcie pojedynczego wierzchołka nie ma tej właściwości. Na przykład graf czynnikowo krytyczny to taki, który ma idealne dopasowanie (współczynnik 1) dla każdego usunięcia wierzchołków, ale (ponieważ ma nieparzystą liczbę wierzchołków) sam nie ma idealnego dopasowania. Porównaj hypo- , używane dla grafów, które nie mają właściwości, ale dla których ma to każde usunięcie o jeden wierzchołek.
sześcian
sześcienny: 1. Wykres sześcienny , wykres ośmiu wierzchołków wierzchołków i krawędzi sześcianu.; 2. Wykres hipersześcianu , wielowymiarowe uogólnienie wykresu sześcianu.; 3. Złożony graf sześcienny , utworzony z hipersześcianu przez dodanie pasujących łączących przeciwległe wierzchołki.; 4. Wykres sześcienny przepołowiony , półkwadrat wykresu hipersześcianu.; 5. Sześcian częściowy , zachowujący odległość podgraf hipersześcianu.; 6. Sześcian grafu $G$ to potęga grafu $G 3$ .; 7. Graf sześcienny , inna nazwa grafu $3$ -regularnego, w którym każdy wierzchołek ma trzy incydentne krawędzie.; 8. Cykle połączone sześcianem , graf sześcienny utworzony przez zastąpienie każdego wierzchołka hipersześcianu cyklem.
cut: cut Przecięcie to podział wierzchołków grafu na dwa podzbiory lub zbiór (znany również jako zbiór przekrojów) krawędzi obejmujących taki podział, jeśli ten zbiór nie jest pusty. Mówi się, że krawędź obejmuje partycję, jeśli ma punkty końcowe w obu podzbiorach. Zatem usunięcie zbioru przekrojów z połączonego grafu powoduje jego rozłączenie.
-set
punkt cięcia: Zobacz punkt artykulacyjny .
Przestrzeń cięcia: Przestrzeń cięcia grafu to GF(2) - przestrzeń wektorowa , której elementami są zbiory przekrojów s grafu, a operacją dodawania wektorów jest symetryczna różnica zbiorów.
cykl: 1. Cykl może być rodzajem wykresu lub rodzajem spaceru . Jako spacer może to być spacer zamknięty (zwany także wycieczką) . ) lub częściej zamknięty spacer bez powtarzających się wierzchołków, aw konsekwencji krawędzi (zwany także prostym cyklem). W tym drugim przypadku jest zwykle traktowany jako graf, tj. wybory pierwszego wierzchołka i kierunku są zwykle uważane za nieistotne; to znaczy cykliczne permutacje i odwrócenia spaceru dają ten sam cykl. Do ważnych specjalnych rodzajów cykli należą cykle Hamiltona , cykle indukowane , cykle obwodowe i najkrótszy cykl, który określa obwód wykresu . Cykl $k$ to cykl o długości $k$ ; na przykład $2$ to dwukąt , a cykl $3$ to trójkąt. Wykres cyklu to wykres, który sam w sobie jest prostym cyklem; wykres cyklu z $n$ wierzchołkami jest zwykle oznaczany jako $C n$ .; 2. Przestrzeń cykli jest przestrzenią wektorową generowaną przez proste cykle na grafie, często na polu 2 elementów, ale także na innych polach.

D

DAG: Skrót od skierowanego grafu acyklicznego , skierowanego wykresu bez żadnych skierowanych cykli.
talia: Wielozbiór grafów utworzony z pojedynczego grafu $G$ poprzez usunięcie pojedynczego wierzchołka na wszystkie możliwe sposoby, zwłaszcza w kontekście hipotezy rekonstrukcji . Pokład krawędziowy jest tworzony w ten sam sposób, usuwając pojedynczą krawędź na wszystkie możliwe sposoby. Grafy w talii są również nazywane kartami . Zobacz także krytyczne (wykresy, które mają właściwość, której nie posiada żadna karta) i hipo- (wykresy, które nie mają właściwości posiadanej przez wszystkie karty).
rozkład: Zobacz rozkład drzewa , rozkład ścieżki lub rozkład gałęzi .
degeneracja
zdegenerowana: Graf $k$ -zdegenerowany jest grafem nieskierowanym, w którym każdy podgraf indukowany ma co najwyżej stopień minimalny $k$ . Degeneracja wykresu to najmniejsze $k$ , dla którego jest to $k$ -zdegenerowany. Uporządkowanie degeneracyjne to uporządkowanie wierzchołków w taki sposób, że każdy wierzchołek ma minimalny stopień w jego indukowanym podgrafie i we wszystkich późniejszych wierzchołkach; w uporządkowaniu degeneracyjnym $k$ - zdegenerowanego grafu każdy wierzchołek ma co najwyżej $k$ późniejszych sąsiadów. Degeneracja jest również znana jako $k$ - liczba rdzeni, szerokość i powiązanie, a jeden plus degeneracja jest również nazywana liczbą kolorystyczną lub liczbą Szekeresa-Wilfa. Grafy $k$ -zdegenerowane nazywane są także grafami $k -indukcyjnymi.$
stopień: 1. Stopień wierzchołka grafu to liczba incydentnych krawędzi. Stopień grafu $G$ (lub jego maksymalny stopień) to maksimum stopni jego wierzchołków, często oznaczane jako $Δ(G)$ ; minimalny stopień $G$ jest minimalnym stopniem jego wierzchołków, często oznaczanym jako $δ (G)$ . Stopień jest czasem nazywany wartościowością ; stopień $v$ w $G$ można oznaczyć $d G (v)$ , $d (G)$ lub $deg(v)$ . Całkowity stopień jest sumą stopni wszystkich wierzchołków; na mocy lematu dotyczącego uzgadniania jest to liczba parzysta. Sekwencja stopni to zbiór stopni wszystkich wierzchołków, posortowanych od największego do najmniejszego. W grafie skierowanym można wyróżnić stopień wejściowy (liczba krawędzi przychodzących) i stopień wyjściowy (liczba krawędzi wychodzących).; 2. Stopień homomorfizmu grafu jest synonimem jego liczby Hadwigera , rzędu największej kliki mniejszej.
Δ, δ: $Δ (G)$ (używając greckiej litery delta) to maksymalny stopień wierzchołka w $G$ , a $δ (G)$ to stopień minimalny; patrz stopień .
gęstość: W grafie o n węzłach gęstość jest stosunkiem liczby krawędzi grafu do liczby krawędzi pełnego grafu w n węzłach. Zobacz gęsty wykres .
głębokość: Głębokość węzła w ukorzenionym drzewie to liczba krawędzi na ścieżce od korzenia do węzła. Na przykład głębokość korzenia wynosi 0, a głębokość dowolnego sąsiedniego węzła wynosi 1. Jest to poziom węzła minus jeden. Należy jednak zauważyć, że niektórzy autorzy zamiast tego używają głębokości jako synonimu poziomu węzła .
średnica: Średnica połączonego wykresu to maksymalna długość najkrótszej ścieżki . Oznacza to, że jest to maksymalna odległość między parami wierzchołków grafu. Jeśli wykres ma wagi na swoich krawędziach, to jego ważona średnica mierzy długość ścieżki jako sumę wag krawędzi wzdłuż ścieżki, podczas gdy nieważona średnica mierzy długość ścieżki przez liczbę krawędzi. W przypadku grafów rozłączonych definicje są różne: średnica może być zdefiniowana jako nieskończona lub jako największa średnica połączonego komponentu lub może być nieokreślona.
diament: Graf diamentowy jest grafem nieskierowanym z czterema wierzchołkami i pięcioma krawędziami.
rozłączony: Silnie połączony _ . (Nie mylić z rozłączonym )
Digon: Digon to prosty cykl o długości dwa w grafie skierowanym lub multigrafie. Digony nie mogą występować w prostych grafach nieskierowanych, ponieważ wymagają dwukrotnego powtórzenia tej samej krawędzi, co narusza definicję prostego .
digraph: Synonim skierowanego wykresu .
dipath: Zobacz ścieżkę skierowaną .
bezpośredni poprzednik: Ogon skierowanej krawędzi, której wierzchołkiem jest dany wierzchołek.
bezpośredni następca: Głowa skierowanej krawędzi, której ogonem jest dany wierzchołek.
skierowany: Graf skierowany to taki, w którym krawędzie mają określony kierunek, od jednego wierzchołka do drugiego. W grafie mieszanym skierowana krawędź to znowu taka, która ma wyróżniony kierunek; skierowane krawędzie można również nazwać łukami lub strzałkami.
skierowany łuk: Patrz strzałka .
skierowana krawędź: Patrz strzałka .
linia skierowana: Patrz strzałka .
skierowana ścieżka: Ścieżka , w której wszystkie krawędzie ten sam kierunek . $Jeśli$ skierowana ścieżka prowadzi od wierzchołka $x$ do wierzchołka $y$ , $x$ jest poprzednikiem y , $y$ jest następnikiem x , a mówi się, że $y$ $jest$ osiągalne z $x$ .
kierunek: 1. Asymetryczna relacja między dwoma sąsiednimi wierzchołkami w grafie , reprezentowana jako an strzałka .; 2. Relacja asymetryczna między dwoma wierzchołkami na ścieżce skierowanej .
rozłączyć: Przyczyna rozłączenia .
odłączony: Nie podłączony .
rozłączny: 1. Dwa podgrafy są rozłączne krawędziowo, jeśli nie mają wspólnych krawędzi, i rozłączne wierzchołkowo, jeśli nie mają wspólnych wierzchołków.; 2. Suma rozłączna dwóch lub więcej grafów to graf, którego zbiory wierzchołków i krawędzi są sumami rozłącznymi odpowiednich zbiorów.
odległość: Odległość _ między dowolnymi dwoma wierzchołkami grafu to długość najkrótszej ścieżki, której wierzchołki są punktami końcowymi.
domatic: Domatyczny podział grafu to podział wierzchołków na zbiory dominujące. Liczba domatyczna grafu to maksymalna liczba zestawów dominujących w takim podziale.
dominujący: Zestaw dominujący jest zbiorem wierzchołków, który zawiera lub sąsiaduje z każdym wierzchołkiem na grafie; nie mylić z pokryciem wierzchołków , zbiorem wierzchołków, który występuje na wszystkich krawędziach grafu. Ważne specjalne typy zbiorów dominujących obejmują niezależne zbiory dominujące (zbiory dominujące, które są również zbiorami niezależnymi) i połączone zbiory dominujące (zbiory dominujące, które indukowały połączone podgrafy). Zbiór dominujący z pojedynczym wierzchołkiem można również nazwać wierzchołkiem uniwersalnym. Liczba dominacji grafu to liczba wierzchołków w najmniejszym zbiorze dominującym.
dual: Graf dualny grafu płaskiego $G$ jest grafem, który ma wierzchołek dla każdej ściany $G$ .

mi

E: $E (G)$ jest zbiorem krawędzi $G$ ; patrz zestaw krawędzi .
ucho: Ucho grafu to ścieżka, której punkty końcowe mogą się pokrywać, ale poza tym nie ma powtórzeń wierzchołków ani krawędzi.
dekompozycja ucha: Dekompozycja ucha to podział krawędzi wykresu na sekwencję uszów, z których każdy punkt końcowy (po pierwszym) należy do poprzedniego ucha i każdy z punktów wewnętrznych nie należy do żadnego poprzedniego ucha. Ucho otwarte to prosta ścieżka (ucho bez powtarzających się wierzchołków), a rozkład ucha otwartego to rozkład ucha, w którym każde ucho po pierwszym jest otwarte; graf ma rozkład otwartego ucha wtedy i tylko wtedy, gdy jest podwójnie spójny. Ucho jest nieparzyste, jeśli ma nieparzystą liczbę krawędzi, a rozkład ucha nieparzystego to rozkład ucha, w którym każde ucho jest nieparzyste; wykres ma nieparzystą dekompozycję ucha wtedy i tylko wtedy, gdy jest czynnikowo krytyczny.
ekscentryczność: Ekscentryczność wierzchołka to największa odległość od niego do dowolnego innego wierzchołka.
krawędź: Krawędź jest (obok wierzchołków) jedną z dwóch podstawowych jednostek, z których zbudowane są grafy. Każda krawędź ma dwa (lub w hipergrafach więcej) wierzchołki, do których jest przymocowana, zwane punktami końcowymi. Krawędzie mogą być skierowane lub nieukierunkowane; krawędzie nieukierunkowane są również nazywane liniami, a krawędzie skierowane są również nazywane łukami lub strzałkami. W nieskierowanym grafie prostym , krawędź może być reprezentowana jako zbiór jej wierzchołków, aw skierowanym grafie prostym może być reprezentowana jako uporządkowana para wierzchołków. Krawędź łącząca wierzchołki $x$ i $y$ jest czasami zapisywana jako $xy$ .
edge cut: Zbiór krawędzi s , których usunięcie rozłącza graf . Jednokrawędziowe cięcie nazywane jest mostem , przesmykiem lub krawędzią tnącą .
zbiór krawędzi: Zbiór krawędzi danego grafu $G$ , czasami oznaczany przez $E (G)$ .
graf bez krawędzi: Graf bez krawędzi lub graf całkowicie rozłączony na danym zbiorze wierzchołków to graf, który nie ma krawędzi. Czasami nazywany jest grafem pustym, ale termin ten może również odnosić się do grafu bez wierzchołków.
osadzanie: Osadzanie grafu jest topologiczną reprezentacją grafu jako podzbioru przestrzeni topologicznej, w której każdy wierzchołek jest reprezentowany jako punkt, a każda krawędź jest reprezentowana jako krzywa, której punkty końcowe krawędzi są punktami końcowymi krzywej, a żadne inne przecięcia między wierzchołkami lub krawędzie. Graf planarny jest grafem, który ma takie osadzenie na płaszczyźnie euklidesowej, a graf toroidalny to graf, który ma takie osadzenie na torusie. Rodzaj wykresu to minimalny możliwy rodzaj dwuwymiarowej rozmaitości , w której można go osadzić.
graf pusty: 1. Graf bez krawędzi na niepustym zbiorze wierzchołków.; 2. Graf rzędu zerowego , graf bez wierzchołków i krawędzi.
koniec: Koniec _ nieskończonego wykresu to klasa równoważności promieni, w której dwa promienie są równoważne, jeśli istnieje trzeci promień, który zawiera nieskończenie wiele wierzchołków z obu z nich.
punkt końcowy: Jeden z dwóch wierzchołków połączonych daną krawędzią lub jeden z pierwszych lub ostatnich wierzchołków spaceru, szlaku lub ścieżki. Pierwszy punkt końcowy danej skierowanej krawędzi nazywany jest ogonem , a drugi punkt końcowy nazywany jest głową .
wyliczanie: Wyliczanie wykresów jest problemem liczenia grafów w danej klasie grafów w funkcji ich kolejności. Mówiąc bardziej ogólnie, problemy z wyliczaniem mogą odnosić się albo do problemów związanych z liczeniem pewnej klasy obiektów kombinatorycznych (takich jak kliki, niezależne zbiory, kolorowanie lub drzewa rozpinające), albo z algorytmicznym wyliczaniem wszystkich takich obiektów.
Eulera: Ścieżka Eulera to spacer, który wykorzystuje każdą krawędź grafu dokładnie raz. Obwód Eulera (zwany także cyklem Eulera lub trasą Eulera) to zamknięty spacer, który wykorzystuje każdą krawędź dokładnie raz. Graf Eulera to graf, który ma obwód Eulera. W przypadku grafu nieskierowanego oznacza to, że graf jest spójny i każdy wierzchołek ma parzysty stopień. W przypadku grafu skierowanego oznacza to, że graf jest silnie spójny i każdy wierzchołek ma stopień wejściowy równy stopniowi wyjściowemu. W niektórych przypadkach wymagania dotyczące łączności są poluzowane, a graf spełniający tylko wymagania stopnia jest nazywany eulerowskim.
nawet: podzielne przez dwa; na przykład cykl parzysty to cykl, którego długość jest parzysta.
ekspander: Graf ekspandera to graf, którego ekspansja krawędzi, ekspansja wierzchołków lub ekspansja widmowa jest ograniczona od zera.
rozwinięcie: 1. Rozszerzenie krawędzi, liczba izoperymetryczna lub stała Cheegera grafu $G$ jest minimalnym stosunkiem liczby krawędzi wychodzących z $S$ do liczby wierzchołków w $S na podzbiorach$ $S$ co najwyżej połowy wierzchołków $G$ .; 2. Ekspansja wierzchołków, liczba izoperymetryczna wierzchołków lub powiększenie grafu $G$ to minimalny stosunek, w podzbiorach $S$ co najwyżej połowy wierzchołków $G$ , liczby wierzchołków na zewnątrz, ale przylegających do $S$ , do liczby wierzchołków w $S.$ _; 3. Jednoznaczna ekspansja sąsiadów grafu $G$ to minimalny stosunek, w podzbiorach co najwyżej połowy wierzchołków $G$ , do liczby wierzchołków poza $S$ , ale sąsiadujących z unikalnym wierzchołkiem w $S$ do liczby wierzchołków w $S$ .; 4. Rozszerzenie widmowe $d$ -regularnego wykresu $G$ jest widmową przerwą między największą wartością własną $d$ jego macierzy sąsiedztwa a drugą co do wielkości wartością własną.; 5. Rodzina grafów ma ograniczoną ekspansję , jeśli wszystkie jej $r$ -płytkie drugorzędne mają stosunek krawędzi do wierzchołków ograniczonych funkcją $r$ , oraz rozwinięcie wielomianowe, jeśli funkcja $r$ jest wielomianem.

F

ściana: W grafie płaskim lub osadzeniu grafu , spójny składnik podzbioru płaszczyzny lub powierzchni osadzania, który jest rozłączny z wykresem. W przypadku osadzania w płaszczyźnie wszystkie ściany oprócz jednej będą ograniczone; jedyna wyjątkowa twarz, która rozciąga się w nieskończoność, nazywana jest zewnętrzną twarzą.
czynnik: Czynnik grafu to podgraf rozpinający: podgraf zawierający wszystkie wierzchołki grafu. Termin ten jest używany przede wszystkim w kontekście podgrafów regularnych: współczynnik $k$ jest czynnikiem, który jest $k$ -regularny. W szczególności $1$ -factor to to samo, co idealne dopasowanie. Graf czynnikowo-krytyczny to graf, dla którego usunięcie dowolnego wierzchołka daje graf o współczynniku $1$ .
faktoryzacja: Graf faktoryzacja to podział krawędzi grafu na czynniki; k $-$ faktoryzacja to podział na $k$ -czynniki. Na przykład $1$ to kolorowanie krawędzi z dodatkową właściwością, że każdy wierzchołek jest incydentny z krawędzią każdego koloru.
rodzina: Synonim klasy .
skończone: Graf jest skończony, jeśli ma skończoną liczbę wierzchołków i skończoną liczbę krawędzi. Wiele źródeł zakłada, że wszystkie grafy są skończone, nie mówiąc o tym wprost. Graf jest lokalnie skończony, jeśli każdy wierzchołek ma skończoną liczbę incydentnych krawędzi. Graf nieskończony to graf, który nie jest skończony: ma nieskończenie wiele wierzchołków, nieskończenie wiele krawędzi lub jedno i drugie.
first order Logika: pierwszego rzędu grafów jest formą logiki, w której zmienne reprezentują wierzchołki wykresu i istnieje predykat binarny do sprawdzania, czy dwa wierzchołki sąsiadują. Należy odróżnić od logiki drugiego rzędu, w której zmienne mogą również reprezentować zbiory wierzchołków lub krawędzi.
-flap: Dla zbioru wierzchołków $X$ , $X$ -flap jest spójną składową indukowanego podgrafu utworzonego przez usunięcie $X$ . Terminologia klap jest powszechnie używana w kontekście przystani , funkcji, które odwzorowują małe zestawy wierzchołków na ich klapy. Zobacz także most cyklu, który jest albo klapą wierzchołków cyklu, albo cięciwą cyklu.
zabronione: Charakterystyka grafów zabronionych to charakterystyka rodziny grafów jako grafów, które nie mają pewnych innych grafów jako podgrafów, podgrafów indukowanych lub drugorzędnych. Jeśli $H$ jest jednym z grafów, który nie występuje jako podgraf, podgraf indukowany lub podrzędny, to mówi się, że $H$ jest zabroniony.
Graf wymuszający: Graf wymuszający jest grafem $H$ takim, że ocena gęstości podgrafu $H$ na wykresach sekwencji grafu $G(n)$ wystarczy do sprawdzenia, czy ta sekwencja jest quasi-losowa .
las: Las to graf nieskierowany bez cykli (rozłączny związek drzew nieukorzenionych) lub graf skierowany utworzony jako rozłączny związek drzew ukorzenionych .
Frucht: 1. Robert Frucht; 2. Graf Fruchta , jeden z dwóch najmniejszych grafów sześciennych bez nietrywialnych symetrii.; 3. Twierdzenie Fruchta , że każda grupa skończona jest grupą symetrii grafu skończonego.
pełny: synonim indukowany .
Graf funkcjonalny: Graf funkcjonalny to graf skierowany, w którym każdy wierzchołek ma stopień jeden. Równoważnie, wykres funkcjonalny jest maksymalnie skierowanym pseudolasem.

G

G: Zmienna często używana do oznaczenia wykresu.
rodzaj: Rodzaj grafu to minimalny rodzaj powierzchni, na której można go osadzić; zobacz osadzanie .
geodezyjny: Jako rzeczownik, geodezyjny jest synonimem najkrótszej ścieżki . Kiedy jest używany jako przymiotnik, oznacza to związane z najkrótszymi ścieżkami lub najkrótszymi odległościami ścieżek.
olbrzym: W teorii grafów losowych element olbrzym jest połączonym składnikiem, który zawiera stały ułamek wierzchołków grafu. W standardowych modelach grafów losowych zazwyczaj występuje co najwyżej jeden gigantyczny składnik.
obwód: Obwód wykresu to długość jego najkrótszego cyklu .
graf: Podstawowy przedmiot badań w teorii grafów, układ wierzchołków połączonych parami krawędziami. Często dzieli się na grafy skierowane lub grafy nieskierowane w zależności od tego, czy krawędzie mają orientację, czy nie. Grafy mieszane obejmują oba rodzaje krawędzi.
chciwy: Utworzony przez chciwy algorytm . Na przykład chciwa kolorystyka Grafu to kolorowanie utworzone przez rozważenie wierzchołków w pewnej kolejności i przypisanie każdemu wierzchołkowi pierwszego dostępnego koloru.
Grötzsch: 1. Herbert Grötzsch; 2. Graf Grötzsch , najmniejszy graf bez trójkątów wymagający czterech kolorów w dowolnym odpowiednim kolorze.; 3. Twierdzenie Grötzscha , że grafy planarne bez trójkątów można zawsze pokolorować co najwyżej trzema kolorami.
Liczba Grundy'ego: 1. Liczba Grundy'ego wykresu to maksymalna liczba kolorów wytwarzanych przez zachłanne kolorowanie , ze źle dobranym uporządkowaniem wierzchołków.

H

H: Zmienna często używana do oznaczenia wykresu, zwłaszcza gdy inny wykres został już oznaczony przez $G$ .
H -kolorowanie: H -kolorowanie grafu $G$ (gdzie $H$ $jest$ również grafem) jest homomorfizmem od $H$ do $G$ .
H -wolny: Graf jest wolny $od H$ , jeśli nie ma podgrafu indukowanego izomorficznego z $H$ , to znaczy, jeśli $H$ jest podgrafem indukowanym zakazanym. H $_$ Grafy -wolne to rodzina wszystkich grafów (lub często wszystkich grafów skończonych), które są wolne od $H.$ Na przykład grafy bez trójkątów to grafy, które nie mają wykresu trójkątnego jako podgrafu. Właściwość bycia $H$ jest zawsze dziedziczna. Graf jest $H -moll$ , jeśli nie ma izomorfiki minorowej z $H.$
Hadwiger: 1. Hugo Hadwiger; 2. Liczba Hadwigera wykresu jest rzędem największego kompletnego drugorzędnego wykresu. Jest również nazywany liczbą kliki skurczu lub stopniem homomorfizmu.; 3. Hipoteza Hadwigera to hipoteza, że liczba Hadwigera nigdy nie jest mniejsza niż liczba chromatyczna.
Hamiltonian: Ścieżka Hamiltona lub cykl Hamiltona jest prostą ścieżką obejmującą lub prostym cyklem obejmującym: pokrywa wszystkie wierzchołki grafu dokładnie raz. Graf jest hamiltonowski, jeśli zawiera cykl hamiltonowski, i identyfikowalny, jeśli zawiera ścieżkę hamiltonowską.
przystań: A $k$ - przystań jest funkcją, która odwzorowuje każdy zestaw $X$ o mniej niż $k$ wierzchołkach na jedną z jego klapek, często spełniając dodatkowe warunki spójności. Kolejność raju to liczba $k$ . Przystani można użyć do scharakteryzowania szerokości drzewa grafów skończonych oraz końców i liczb Hadwigera grafów nieskończonych.
wysokość: 1. Wysokość węzła w drzewie ukorzenionym to liczba krawędzi na najdłuższej ścieżce, odchodzącej od korzenia (tzn. jej węzły mają ściśle rosnącą głębokość), która zaczyna się w tym węźle i kończy na liściu.; 2. Wysokość ukorzenionego drzewa to wysokość jego korzenia. Oznacza to, że wysokość drzewa to liczba krawędzi na najdłuższej możliwej ścieżce, odchodzącej od korzenia, która zaczyna się od korzenia i kończy na liściu.; 3. Wysokość skierowanego grafu acyklicznego jest maksymalną długością skierowanej ścieżki w tym grafie.
dziedziczna: Własność dziedziczna grafów to własność, która jest domknięta pod grafami indukowanymi: jeśli $G$ ma własność dziedziczną, to musi nią być każdy indukowany podgraf $G$ . Porównaj monotonnie (zamknięty pod wszystkimi podgrafami) lub nieletni-zamknięty (zamknięty pod nieletnimi).
sześciokąt: Prosty cykl składający się z dokładnie sześciu krawędzi i sześciu wierzchołków.
dziura: Dziura jest indukowanym cyklem o długości co najmniej czterech. Dziura nieparzysta to dziura nieparzystej długości. Antydziura jest indukowanym podgrafem rzędu czwartego, którego dopełnieniem jest cykl; równoważnie jest to dziura w wykresie dopełniacza. Ta terminologia jest używana głównie w kontekście grafów doskonałych, które charakteryzują się silnym twierdzeniem o grafie doskonałym jako grafy bez nieparzystych dziur lub nieparzystych antydziur. Wykresy bez dziur są takie same jak wykresy akordowe .
równoważność homomorficzna: Dwa grafy są homomorficznie równoważne, jeśli istnieją dwa homomorfizmy, po jednym z każdego grafu do drugiego.
homomorfizm: 1. Homomorfizm grafu to odwzorowanie zbioru wierzchołków jednego grafu na zbiór wierzchołków innego grafu, które odwzorowuje sąsiednie wierzchołki na sąsiednie wierzchołki. Ten typ mapowania między grafami jest najczęściej używany w podejściach opartych na teorii kategorii do teorii grafów. Właściwe kolorowanie grafu można równoważnie opisać jako homomorfizm pełnego grafu.; 2. Stopień homomorfizmu grafu jest synonimem jego liczby Hadwigera , rzędu największej kliki mniejszej.
hyperarc: Ukierunkowana hiperkrawędź posiadająca zestaw źródłowy i docelowy.
hyperedge: Krawędź w hipergrafie , mająca dowolną liczbę punktów końcowych, w przeciwieństwie do wymogu , aby krawędzie grafów miały dokładnie dwa punkty końcowe.
hipersześcian: Graf hipersześcianu to graf utworzony z wierzchołków i krawędzi geometrycznego hipersześcianu .
hipergraf: A hipergraf to uogólnienie grafu, w którym każda krawędź (zwana w tym kontekście hiperkrawędzią) może mieć więcej niż dwa punkty końcowe.
hypo-: Ten przedrostek, w połączeniu z właściwością grafu, wskazuje graf, który nie ma tej właściwości, ale taki, że każdy podgraf utworzony przez usunięcie pojedynczego wierzchołka ma tę właściwość. Na przykład graf hipohamiltonowski to taki, który nie ma cyklu Hamiltona, ale dla którego każde usunięcie jednego wierzchołka tworzy podgraf Hamiltona. Porównaj krytyczne , używane do grafów, które mają właściwość, ale dla których nie ma każdego usunięcia jednego wierzchołka.

I

w stopniach: Liczba krawędzi przychodzących w grafie skierowanym; patrz stopień .
częstość występowania: Częstość występowania w grafie to para wierzchołek-krawędź taka, że wierzchołek jest punktem końcowym krawędzi.
macierz incydentów: Macierz incydentów grafu to macierz, której wiersze są indeksowane przez wierzchołki grafu, a kolumny przez krawędzie, z jedynką w komórce dla wiersza i $i$ kolumny $j$ , gdy wierzchołek $i$ i krawędź $j$ pokrywają się, i zero w przeciwnym razie.
incydent: Relacja między krawędzią a jednym z jej punktów końcowych.
nieporównywalność: Graf nieporównywalności jest uzupełnieniem grafu porównywalności ; patrz porównywalność .
niezależny: 1. Niezależny zbiór to zbiór wierzchołków, który indukuje podgraf bez krawędzi. Można go również nazwać stabilnym zestawem lub coclique. Liczba niezależności $α (G)$ jest wielkością maksymalnego zbioru niezależnego .; 2. W matrycy graficznej grafu podzbiór krawędzi jest niezależny, jeśli odpowiadający mu podgraf jest drzewem lub lasem. W dwukołowym matroidzie podzbiór krawędzi jest niezależny, jeśli odpowiadający mu podwykres jest pseudolasem .
obojętność: Wykres obojętności to inna nazwa właściwego wykresu interwałowego lub wykresu interwałowego jednostkowego; patrz właściwe .
indukowany: Podgraf indukowany lub pełny podgraf grafu to podgraf utworzony z podzbioru wierzchołków i wszystkich krawędzi, które mają oba punkty końcowe w podzbiorze. Szczególne przypadki obejmują ścieżki indukowane i cykle indukowane , podgrafy indukowane, które są ścieżkami lub cyklami.
indukcyjny: Synonim słowa zdegenerowany .
nieskończony: Graf nieskończony to taki, który nie jest skończony; patrz skończony .
wewnętrzny: Wierzchołek ścieżki lub drzewa jest wewnętrzny, jeśli nie jest liściem; to znaczy, jeśli jego stopień jest większy niż jeden. Dwie ścieżki są wewnętrznie rozłączne (niektórzy nazywają to niezależnymi ), jeśli nie mają żadnego wspólnego wierzchołka, z wyjątkiem pierwszego i ostatniego.
skrzyżowanie: 1. Punkt przecięcia dwóch grafów jest ich największym wspólnym podgrafem, grafem utworzonym przez wierzchołki i krawędzie należące do obu grafów.; 2. Graf przecięcia to graf, którego wierzchołki odpowiadają zbiorom lub obiektom geometrycznym, z krawędzią między dwoma wierzchołkami dokładnie wtedy, gdy odpowiednie dwa zbiory lub obiekty mają niepuste przecięcie. Kilka klas grafów można zdefiniować jako grafy przecięć pewnych typów obiektów, na przykład grafy cięciw (wykresy przecięć poddrzew drzewa), grafy kołowe (wykresy przecięć cięciw koła), grafy interwałowe (wykresy przecięć odcinków linii), wykresy liniowe (wykresy przecięć krawędzi grafu) i wykresy klik (wykresy przecięć maksymalnych klik wykresu). Każdy graf jest grafem przecięcia dla pewnej rodziny zbiorów, a rodzina ta nazywana jest reprezentacją przecięcia grafu. Numer przecięcia grafu $G$ to minimalna całkowita liczba elementów w dowolnej reprezentacji przecięcia grafu $G$ .
interwał: 1. Wykres interwałowy jest wykresem przecięcia odstępy linii .; 2. Przedział $[u, v]$ na grafie jest sumą wszystkich najkrótszych ścieżek od $u$ do $v$ .; 3. Grubość interwału jest synonimem szerokości ścieżki .
niezmienny: Synonim właściwości .
odwrócona strzałka: Strzałka o przeciwnym kierunku w stosunku do innej strzałki. Strzałka $(y, x)$ jest odwróconą strzałką $(x, y)$ .
izolowany: Odosobniony wierzchołek grafu to wierzchołek, którego stopień wynosi zero, czyli wierzchołek bez incydentnych krawędzi.
izomorficzny: Dwa grafy są izomorficzne, jeśli występuje między nimi izomorfizm; zobacz izomorfizm .
izomorfizm: Izomorfizm grafów to zgodność wierzchołków i krawędzi jednego grafu z wierzchołkami i krawędziami innego grafu zachowująca incydencje jeden do jednego. O dwóch grafach powiązanych w ten sposób mówimy, że są izomorficzne.
izoperymetryczny: Zobacz rozwinięcie .
przesmyk: Synonim mostu w znaczeniu krawędzi, której usunięcie rozłącza wykres.

k

K: Notacja pełnych grafów, pełnych grafów dwudzielnych i pełnych grafów wielodzielnych znajduje się w rozdziale .
κ: $κ (G)$ (używając greckiej litery kappa) jest rzędem maksymalnej kliki w $G$ ; zobacz klikę .
Jądro: Jądro grafu skierowanego to zbiór wierzchołków, który jest zarówno stabilny , jak i absorbujący .
węzeł: Nieunikniona część grafu skierowanego . Zobacz węzeł (matematyka) i teoria węzłów .

Ł

L: $L (G)$ jest wykresem liniowym $G$ ; patrz wiersz .
etykieta: 1. Informacja związana z wierzchołkiem lub krawędzią grafu. Graf etykietowany to graf, którego wierzchołki lub krawędzie mają etykiety. Terminy oznaczone wierzchołkami lub oznaczone krawędziami mogą być użyte do określenia, które obiekty grafu mają etykiety. Etykietowanie wykresów odnosi się do kilku różnych problemów związanych z przypisywaniem etykiet do wykresów podlegających pewnym ograniczeniom. Zobacz także kolorowanie wykresów , w którym etykiety są interpretowane jako kolory.; 2. W kontekście wyliczania grafów mówi się, że wierzchołki grafu są oznakowane, jeśli można je od siebie odróżnić. Na przykład można to uczynić prawdą, ustalając zgodność jeden do jednego między wierzchołkami a liczbami całkowitymi od 1 do rzędu grafu. Kiedy wierzchołki są oznaczone, grafy, które są względem siebie izomorficzne (ale z różnymi uporządkowaniami wierzchołków) są liczone jako oddzielne obiekty. W przeciwieństwie do tego, gdy wierzchołki nie są oznaczone, grafy, które są względem siebie izomorficzne, nie są liczone oddzielnie.
liść: 1. Wierzchołek liścia lub wierzchołek wiszący (zwłaszcza na drzewie) to wierzchołek, którego stopień wynosi $1$ . Krawędź liścia lub krawędź wisząca to krawędź łącząca wierzchołek liścia z jego pojedynczym sąsiadem.; 2. Potęga liści drzewa to graf, którego wierzchołkami są liście drzewa, a krawędzie łączą liście, których odległość w drzewie jest co najwyżej zadaną wartością progową.
długość: W grafie nieważonym długość cyklu, ścieżki lub spaceru to liczba krawędzi, z których korzysta. Na grafie ważonym może to być zamiast tego suma wag krawędzi, których używa. Długość służy do określenia najkrótszej ścieżki , obwód (najkrótsza długość cyklu) i najdłuższa ścieżka między dwoma wierzchołkami grafu.
poziom: 1. Jest to głębokość węzła plus 1, chociaż niektórzy określają ją jako synonim głębokości . Poziom węzła w zakorzenionym drzewie to liczba węzłów na ścieżce od korzenia do węzła. Na przykład korzeń ma poziom 1, a każdy z sąsiednich węzłów ma poziom 2.; 2. Zbiór wszystkich węzłów o tym samym poziomie lub głębokości.
linia: Synonim nieskierowanej krawędzi. Wykres liniowy $L (G)$ Grafu $G$ jest grafem, którego wierzchołkiem jest każda krawędź $G$ i krawędź każdej pary krawędzi, które mają wspólny punkt końcowy w $G$ .
linkage: Synonim degeneracji .
lista: 1. Lista sąsiedztwa jest komputerową reprezentacją grafów używaną w algorytmach grafowych.; 2. Kolorowanie listy to odmiana kolorowania grafu, w której każdy wierzchołek ma listę dostępnych kolorów.
lokalny: Właściwość lokalna grafu to właściwość określona tylko przez sąsiedztwo wierzchołków w grafie. Na przykład graf jest lokalnie skończony, jeśli wszystkie jego sąsiedztwa są skończone.
pętla: Pętla lub samopętla to krawędź, której oba punkty końcowe są tym samym wierzchołkiem . Tworzy cykl o długości $1$ . Nie są one dozwolone w prostych wykresach.

M

powiększenie Synonim: rozszerzania wierzchołków .
dopasowanie: Dopasowanie to zbiór krawędzi, w których żadne dwie nie mają wspólnego wierzchołka . Wierzchołek jest dopasowany lub nasycony, jeśli jest jednym z punktów końcowych krawędzi w dopasowaniu. Idealne dopasowanie lub pełne dopasowanie to dopasowanie, które pasuje do każdego wierzchołka; można go również nazwać czynnikiem 1 i może istnieć tylko wtedy, gdy kolejność jest parzysta. Prawie idealne dopasowanie w grafie o nieparzystym porządku to takie, które nasyca wszystkie wierzchołki oprócz jednego. Maksymalne dopasowanie to dopasowanie, które wykorzystuje jak najwięcej krawędzi; pasujący numer $α'(G)$ wykresu $G$ to liczba krawędzi w maksymalnym dopasowaniu. Maksymalne dopasowanie to dopasowanie, do którego nie można dodać żadnych dodatkowych krawędzi.
maksymalny: 1. Podwykres danego grafu $G$ jest maksymalny dla określonej własności, jeśli ma tę właściwość, ale żaden inny jego supergraf, który jest również podgrafem $G$ , nie ma tej samej własności. Oznacza to, że jest to maksymalny element podgrafów o tej własności. Na przykład maksymalna klika jest pełnym podgrafem, którego nie można rozwinąć do większego pełnego podgrafu. Słowo „maksymalny” należy odróżnić od „maksymalnego”: maksymalny podwykres jest zawsze maksymalny, ale niekoniecznie odwrotnie.; 2. Graf prosty o danej własności jest maksymalny dla tej własności, jeżeli nie można dodać do niego więcej krawędzi (zachowanie niezmienionego zbioru wierzchołków) przy zachowaniu zarówno prostoty grafu, jak i samej własności. Tak więc, na przykład, maksymalny graf planarny jest grafem planarnym takim, że dodanie do niego większej liczby krawędzi stworzyłoby graf nieplanarny.
maksimum: Podgraf danego grafu $G$ jest maksimum dla określonej właściwości, jeśli jest to największy podgraf (według kolejności lub rozmiaru) spośród wszystkich podgrafów z tą właściwością. Na przykład maksymalna klika to dowolna z największych klik na danym wykresie.
mediana: 1. Mediana trójki wierzchołków, wierzchołek należący do najkrótszych ścieżek między wszystkimi parami wierzchołków, zwłaszcza w grafach medianowych i grafach modularnych .; 2. Graf mediany to graf, w którym każde trzy wierzchołki mają unikalną medianę.
Meyniel: 1. Henri Meyniel, francuski teoretyk grafów.; 2. Graf Meyniela to wykres, w którym każdy nieparzysty cykl o długości pięciu lub więcej ma co najmniej dwa akordy.
minimalny: Podgraf danego grafu jest minimalny dla określonej własności, jeżeli ma tę własność, ale żaden właściwy podgraf tego grafu nie ma tej samej własności. Oznacza to, że jest to minimalny element podgrafów z tą właściwością.; cięcie Przecięcie , którego zestaw cięć ma minimalną całkowitą wagę, ewentualnie ograniczone do cięć oddzielających wyznaczoną parę wierzchołków; charakteryzują się twierdzeniem o maksymalnym przepływie i minimalnym cięciu .
minimalne
drobny: wykres A $H$ jest minorem innego grafu $G$ , jeśli $H$ można otrzymać usuwając krawędzie lub wierzchołki z $G$ i skracając krawędzie w $G$ . Jest płytkim minorem, jeśli można go utworzyć jako minor w taki sposób, że wszystkie podgrafy $G$ , które zostały skrócone w celu utworzenia wierzchołków $H$ , mają małą średnicę. $H$ jest topologiczną drugorzędną G $,$ jeśli $G$ ma podgraf, który $jest$ podpodziałem H . Graf jest $H$ -moll, jeśli nie ma $H$ jako minora. Rodzina grafów jest domknięta na drobne, jeśli jest zamknięta pod nieletnimi; twierdzenie Robertsona – Seymoura charakteryzuje rodziny zamknięte z nieletnimi jako posiadające skończony zbiór zakazanych nieletnich.; graf Graf mieszany to graf, który może zawierać zarówno krawędzie skierowane, jak i nieskierowane.
mieszany
modułowy: 1. Graf modułowy , graf, w którym każda trójka wierzchołków ma co najmniej jeden środkowy wierzchołek należący do najkrótszych ścieżek między wszystkimi parami trójki.; 2. Dekompozycja modułowa , dekompozycja grafu na podgrafy, w których wszystkie wierzchołki łączą się z resztą grafu w ten sam sposób.; 3. Modularność klastrowania grafu, różnica liczby krawędzi między klastrami od jego wartości oczekiwanej.
monotone: Właściwość monotoniczności grafów to własność, która jest domknięta pod grafami: jeśli $G$ ma własność dziedziczną, to musi nią być każdy podgraf $G$ . Porównaj dziedziczne (zamknięte pod wykresami indukowanymi) lub niepełno-zamknięte (zamknięte pod nieletnimi).
Wykres Moore'a: Graf Moore'a to graf regularny, dla którego granica Moore'a jest dokładnie spełniona. Granica Moore'a to nierówność odnosząca się do stopnia, średnicy i rzędu wykresu, udowodniona przez Edwarda F. Moore'a . Każdy graf Moore'a jest klatką.
multigraf: Multigraf to graf, który dopuszcza wiele przylegań (i często pętle własne) ; wykres, który nie musi być prosty.
wielokrotne sąsiedztwo: Wielokrotne sąsiedztwo lub wielokrotna krawędź to zestaw więcej niż jednej krawędzi, z których wszystkie mają te same punkty końcowe (w tym samym kierunku, w przypadku grafów skierowanych). Graf z wieloma krawędziami jest często nazywany multigrafem.
krotność: Krotność krawędzi to liczba krawędzi w wielokrotnym sąsiedztwie. Krotność grafu to maksymalna krotność dowolnej z jego krawędzi.

N

N: 1. Aby zapoznać się z notacją dla otwartych i zamkniętych sąsiedztw, zobacz sąsiedztwo .; 2. Małe $n$ jest często używane (zwłaszcza w informatyce) do oznaczenia liczby wierzchołków w danym grafie.
sąsiad
sąsiad: Wierzchołek, który sąsiaduje z danym wierzchołkiem.
sąsiedztwo
sąsiedztwo: Otwarte sąsiedztwo ( lub sąsiedztwo) wierzchołka $v$ jest podgrafem indukowanym przez wszystkie wierzchołki sąsiadujące z $v$ . Zamknięte sąsiedztwo jest definiowane w ten sam sposób, ale obejmuje również $v$ sam. Otwarte sąsiedztwo $N [v v$ $w$ G $można$ oznaczyć $NG (v)]$ lub $N (v) , a$ zamknięte sąsiedztwo można oznaczyć $NG [v] .$ lub Gdy otwartość lub zamkniętość sąsiedztwa nie jest określona, przyjmuje się, że jest ono otwarte.
sieć: Graf, w którym atrybuty (np. nazwy) są powiązane z węzłami i/lub krawędziami.
węzeł: synonim wierzchołka .
non-edge: Non-edge lub anti-edge to para wierzchołków, które nie sąsiadują ze sobą; krawędzie wykresu dopełniacza.
null graph: Zobacz pusty wykres .

O

nieparzysty: 1. Cykl nieparzysty to cykl, którego długość jest nieparzysta. Nieparzysty obwód grafu niedwudzielnego to długość jego najkrótszego nieparzystego cyklu. Dziwna dziura to szczególny przypadek nieparzystego cyklu: taki, który jest indukowany i ma cztery lub więcej wierzchołków.; 2. Nieparzysty wierzchołek to wierzchołek, którego stopień jest nieparzysty. Zgodnie z lematem o uzgadnianiu każdy skończony graf nieskierowany ma parzystą liczbę nieparzystych wierzchołków.; 3. Ucho nieparzyste to prosta ścieżka lub prosty cykl o nieparzystej liczbie krawędzi, używane w dekompozycjach grafów czynnikowo-krytycznych ucha nieparzystego; patrz ucho .; 4. Akord nieparzysty to krawędź łącząca dwa wierzchołki oddalone od siebie o nieparzystą odległość w cyklu parzystym. Akordy nieparzyste są używane do definiowania silnie akordowych wykresów .; 5. Graf nieparzysty jest szczególnym przypadkiem grafu Knesera , mającym jeden wierzchołek dla każdego podzbioru $(n - 1) elementów zbioru$ $(2 n - 1)$ oraz krawędź łączącą dwa podzbiory, gdy odpowiadające im zbiory są nieskładny.
otwórz: 1. Zobacz sąsiedztwo .; 2. Patrz spacer .
zamówienie: 1. Rząd grafu $G$ to liczba jego wierzchołków, $| V (G)|$ . Zmienna $n$ jest często używana dla tej wielkości. Zobacz także rozmiar , liczbę krawędzi.; 2. Rodzaj logiki grafów ; patrz pierwsze i drugie zamówienie .; 3. Porządek lub uporządkowanie grafu to uporządkowanie jego wierzchołków w ciąg, zwłaszcza w kontekście uporządkowania topologicznego (porządek skierowanego wykresu acyklicznego, w którym każda krawędź przechodzi od wcześniejszego wierzchołka do późniejszego wierzchołka w kolejności) i uporządkowanie degeneracji (kolejność, w której każdy wierzchołek ma minimalny stopień w jego indukowanym podgrafie i we wszystkich późniejszych wierzchołkach).; 4. Aby zapoznać się z kolejnością przystani lub cierni, zobacz przystań i ciernie .
orientacja
zorientowana: 1. Orientacja grafu nieskierowanego to przypisanie kierunków jego krawędziom, czyniąc go grafem skierowanym. Graf zorientowany to taki, któremu przypisano orientację. A więc np polytree jest drzewem zorientowanym; różni się od drzewa skierowanego (arborescencji) tym, że nie ma wymogu spójności w kierunkach jego krawędzi. Inne specjalne typy orientacji obejmują turnieje , orientacje kompletnych wykresów; silne orientacje , orientacje silnie ze sobą powiązane; orientacje acykliczne , orientacje acykliczne; Orientacje eulerowskie , orientacje eulerowskie; i przechodnie orientacje , orientacje, które są przechodnie zamknięte.; 2. Graf zorientowany, używany przez niektórych autorów jako synonim grafu skierowanego .
stopień zewnętrzny: Zobacz stopień .
zewnętrzna: Zobacz twarz .
planar: zewnętrzny Graf planarny to graf, który można osadzić w płaszczyźnie (bez przecięć), tak aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni grafu.

P

ścieżka: Ścieżka może być albo ścieżką, albo ścieżką bez powtarzających się wierzchołków , a co za tym idzie krawędzi (zwaną także prostą), w zależności od źródła. Do ważnych przypadków specjalnych należą ścieżki indukowane i najkrótsze ścieżki .
dekompozycja ścieżki: Dekompozycja ścieżki grafu $G$ jest dekompozycją drzewa, którego podstawowym drzewem jest ścieżka. Jego szerokość definiowana jest analogicznie jak w przypadku dekompozycji drzew, jako o jeden mniejsza od rozmiaru największego worka. Minimalna szerokość dowolnego rozkładu ścieżki $G$ jest szerokością ścieżki $G.$ _
szerokość ścieżki: Szerokość ścieżki grafu $G$ jest minimalną szerokością rozkładu ścieżki $G$ . Można go również zdefiniować w kategoriach liczby kliki zakończenia przedziału $G$ . Zawsze mieści się między szerokością pasma a szerokością drzewa $G$ . Jest również znany jako grubość interwału, liczba separacji wierzchołków lub liczba wyszukiwania węzłów.
zawieszka: Zobacz liść .
doskonały: 1. Doskonały wykres jest grafem, w którym w każdym indukowanym podgrafie liczba chromatyczna jest równa liczbie kliki. Twierdzenie o doskonałym grafie i silne twierdzenie o doskonałym grafie to dwa twierdzenia o doskonałych grafach, przy czym pierwsze dowodzi, że ich uzupełnienia są również doskonałe, a drugie dowodzi, że są to dokładnie grafy bez nieparzystych dziur lub antydziur.; 2. Grafem doskonale uporządkowanym jest graf, którego wierzchołki można uporządkować w taki sposób, że algorytm zachłannego kolorowania z tym uporządkowaniem optymalnie koloruje każdy indukowany podgraf. Grafy doskonale uporządkowane są podklasą grafów doskonałych.; 3. Idealne dopasowanie to dopasowanie, które nasyca każdy wierzchołek; zobacz dopasowanie .; 4. Doskonały rozkład na czynniki 1 to podział krawędzi grafu na idealne dopasowania, tak że każde dwa dopasowania tworzą cykl Hamiltona.
peryferyjny: 1. Cykl peryferyjny lub cykl nierozdzielający to cykl z co najwyżej jednym mostkiem.; 2. Wierzchołek peryferyjny to wierzchołek, którego ekscentryczność jest maksymalna. Na drzewie musi to być liść.
Petersen: 1. Julius Petersen (1839–1910), duński teoretyk grafów.; 2. Graf Petersena , graf z 10 wierzchołkami i 15 krawędziami, często używany jako kontrprzykład.; 3. Twierdzenie Petersena , że każdy bezmostkowy graf sześcienny ma idealne dopasowanie.
planarny: Graf planarny to graf osadzony na płaszczyźnie euklidesowej. Graf płaski to graf planarny, dla którego określone osadzenie zostało już ustalone. Wykres $k$ -płaski to taki, który można narysować na płaszczyźnie z co najwyżej $k$ przecięciami na krawędź.
wielodrzewo: Polytree to drzewo zorientowane; równoważnie skierowany graf acykliczny, którego podstawowym grafem nieskierowanym jest drzewo.
potęga: 1. Potęga grafu $G k$ grafu $G$ jest innym grafem w tym samym zbiorze wierzchołków; dwa wierzchołki sąsiadują ze sobą w $G k$ wtedy, gdy są w odległości co najwyżej $k$ w $G$ . Potęga liści jest blisko spokrewnioną koncepcją, wywodzącą się z potęgi drzewa na podstawie wykresu podrzędnego wywołanego przez liście drzewa.; 2. Analiza wykresu mocy to metoda analizy złożonych sieci poprzez identyfikację klik, bicliques i gwiazd w sieci.; 3. Prawa potęgowe w rozkładach stopni sieci bezskalowych to zjawisko, w którym liczba wierzchołków danego stopnia jest proporcjonalna do potęgi tego stopnia.
poprzednik: Wierzchołek występujący przed danym wierzchołkiem na ścieżce skierowanej .
właściwy: 1. Podgraf właściwy to taki podgraf, który usuwa co najmniej jeden wierzchołek lub krawędź względem całego grafu; w przypadku grafów skończonych właściwe podgrafy nigdy nie są izomorficzne z całym grafem, ale w przypadku grafów nieskończonych mogą być.; 2. Właściwe kolorowanie to przypisanie kolorów wierzchołkom grafu (kolorowanie), które przypisuje różne kolory punktom końcowym każdej krawędzi; patrz kolor .; 3. Właściwy wykres interwałowy lub właściwy wykres łuku kołowego to wykres przecięcia zbioru przedziałów lub łuków kołowych (odpowiednio), tak że żaden przedział ani łuk nie zawiera innego przedziału lub łuku. Właściwe wykresy interwałowe nazywane są również wykresami interwałów jednostkowych (ponieważ zawsze można je przedstawić za pomocą interwałów jednostkowych) lub wykresami obojętności.
właściwość: Właściwość grafu jest czymś, co może być prawdziwe dla niektórych grafów, a fałszywe dla innych, i to zależy tylko od struktury grafu, a nie od przypadkowych informacji, takich jak etykiety. Właściwości grafów można równoważnie opisać w kategoriach klas grafów (wykresów, które mają daną właściwość). Mówiąc bardziej ogólnie, właściwość wykresu może być również funkcją wykresów, która jest ponownie niezależna od przypadkowych informacji, takich jak rozmiar, kolejność lub sekwencja stopni wykresu; ta bardziej ogólna definicja właściwości jest również nazywana niezmiennikiem wykresu.
pseudolas: Pseudolas _ jest grafem nieskierowanym, w którym każdy połączony składnik ma co najwyżej jeden cykl, lub grafem skierowanym, w którym każdy wierzchołek ma co najwyżej jedną krawędź wychodzącą.
pseudograf: Pseudograf to graf lub multigraf, który umożliwia samopętle.

Q

graf quasi-liniowy: Graf quasi-liniowy lub lokalnie dwudzielny to graf, w którym otwarte sąsiedztwo każdego wierzchołka można podzielić na dwie kliki. Wykresy te są zawsze wolne od pazurów i zawierają jako szczególny przypadek wykresy liniowe . Są one używane w teorii struktury grafów bez pazurów.
quasi-losowa sekwencja grafów: quasi -losowa sekwencja grafów to sekwencja grafów, która ma kilka wspólnych właściwości z sekwencją grafów losowych wygenerowanych zgodnie z modelem grafów losowych Erdősa-Rényiego .
kołczan: Kołczan to ukierunkowany multigraf, używany w teorii kategorii . Krawędzie kołczanu nazywane są strzałami.

R

promień: Promień wykresu to minimalna ekscentryczność dowolnego wierzchołka.
Ramanujana: Graf Ramanujana to graf, którego widmowa ekspansja jest możliwie największa. Oznacza to $sąsiedztwa$ że jest to wykres $d -regularny, taki że$ wynosi co najwyżej .
promień: Promień w grafie nieskończonym jest nieskończoną prostą ścieżką z dokładnie jednym punktem końcowym. Końce wykresu to klasy równoważności promieni.
osiągalność: Zdolność przechodzenia z jednego wierzchołka do drugiego w grafie .
osiągalny: Ma afirmatywną osiągalność . Mówimy, że wierzchołek $y$ jest osiągalny z wierzchołka $x$ , jeśli istnieje ścieżka z $x$ do $y$ .
rozpoznawalny: W kontekście domysłu rekonstrukcji , właściwość grafu jest rozpoznawalna, jeśli jej prawdziwość można określić na podstawie talii grafu. Wiadomo, że wiele właściwości wykresu jest rozpoznawalnych. Jeśli hipoteza rekonstrukcji jest prawdziwa, wszystkie właściwości grafu są rozpoznawalne.
rekonstrukcja: Hipoteza rekonstrukcji stwierdza, że każdy nieskierowany graf $G$ jest jednoznacznie określony przez swoją talię , multizbiór grafów utworzony przez usunięcie jednego wierzchołka z $G$ na wszystkie możliwe sposoby. W tym kontekście rekonstrukcja to tworzenie grafu z jego talii.
prostokąt: Prosty cykl składający się dokładnie z czterech krawędzi i czterech wierzchołków.
regularny: Graf jest $d$ -regularny, gdy wszystkie jego wierzchołki mają stopień $d$ . Graf regularny to graf, który jest $d$ -regularny dla pewnego $d$ .
turniej regularny: Turniej regularny to turniej, w którym stopień wejściowy równa się stopniowi zewnętrznemu dla wszystkich wierzchołków.
odwróć: Zobacz transpozycję .
korzeń: 1. Wyznaczony wierzchołek grafu, szczególnie w drzewach skierowanych i grafach ukorzenionych .; 2. Operacja odwrotna do potęgi grafu : $k-$ ty pierwiastek grafu $G$ jest innym grafem w tym samym zbiorze wierzchołków takim, że dwa wierzchołki sąsiadują ze sobą w $G wtedy i tylko wtedy, gdy ich odległość$ w pierwiastku wynosi co najwyżej $k .$

S

drugiego rzędu: Logika drugiego rzędu grafów jest formą logiki, w której zmienne mogą reprezentować wierzchołki, krawędzie, zbiory wierzchołków i (czasami) zbiory krawędzi. Ta logika obejmuje predykaty do sprawdzania, czy wierzchołek i krawędź są przypadkowe, a także czy wierzchołek lub krawędź należą do zbioru. Należy odróżnić od logiki pierwszego rzędu, w której zmienne mogą reprezentować tylko wierzchołki.
nasycony: Zobacz dopasowanie .
liczba wyszukiwania: Numer wyszukiwania węzła jest synonimem szerokości ścieżki .
samopętla: Synonim pętli .
wierzchołek oddzielający: Zobacz punkt artykulacji .
numer separacji: Numer separacji wierzchołków jest synonimem szerokości ścieżki .
prosty: 1. Graf prosty to graf bez pętli i bez wielokrotnych przylegań. Oznacza to, że każda krawędź łączy dwa różne punkty końcowe i żadne dwie krawędzie nie mają takich samych punktów końcowych. Prosta krawędź to krawędź, która nie jest częścią wielokrotnego sąsiedztwa. W wielu przypadkach zakłada się, że wykresy są proste, chyba że określono inaczej.; 2. Prosta ścieżka lub prosty cykl to ścieżka lub cykl, który nie ma powtarzających się wierzchołków, a co za tym idzie, nie ma powtarzających się krawędzi.
zlew: Zlew w grafie skierowanym to wierzchołek bez krawędzi wychodzących (stopień zewnętrzny równa się 0).
rozmiar: Rozmiarem grafu $G$ jest liczba jego krawędzi, $| mi (g)|$ . Zmienna $m$ jest często używana dla tej wielkości. Zobacz także kolejność , liczbę wierzchołków.
sieć małego świata: Sieć małego świata to graf, w którym większość węzłów nie sąsiaduje ze sobą, ale do większości węzłów można dotrzeć z każdego innego węzła za pomocą niewielkiej liczby przeskoków lub kroków. W szczególności sieć małego świata jest definiowana jako graf, w którym typowa odległość L między dwoma losowo wybranymi węzłami (liczba wymaganych kroków) rośnie proporcjonalnie do logarytmu liczby węzłów N w
snark: sieci Snark jest prostą , spójny, bezmostkowy graf sześcienny o indeksie chromatycznym równym 4.
source: Źródłem w grafie skierowanym jest wierzchołek, do którego nie wchodzą żadne krawędzie (w-stopień równa się 0).
przestrzeń: W teorii grafów algebraicznych z grafem można powiązać kilka przestrzeni wektorowych nad polem binarnym . Każdy ma zbiory krawędzi lub wierzchołków dla swoich wektorów i symetryczną różnicę zbiorów jako operację sumy wektorów. Przestrzeń krawędzi to przestrzeń wszystkich zbiorów krawędzi, a przestrzeń wierzchołków to przestrzeń wszystkich zbiorów wierzchołków. Wycięta przestrzeń jest podprzestrzenią przestrzeni brzegowej, której elementami są zbiory przekrojów grafu. Przestrzeń cyklu ma jako swoje elementy podgrafy rozpinające Eulera.
klucz: Klucz jest (zwykle rzadkim) grafem, którego najkrótsze odległości ścieżek są zbliżone do tych w gęstym grafie lub innej przestrzeni metrycznej. Wariacje obejmują klucze geometryczne , wykresy, których wierzchołki są punktami w przestrzeni geometrycznej; klucze do drzew , obejmujące drzewa grafu, którego odległości są zbliżone do odległości grafów, oraz klucze grafów , rzadkie podgrafy gęstego grafu, których odległości są zbliżone do odległości oryginalnego wykresu. Chciwy klucz to klucz grafowy skonstruowany przez zachłanny algorytm, generalnie taki, który uwzględnia wszystkie krawędzie od najkrótszej do najdłuższej i zachowuje te, które są potrzebne do zachowania przybliżenia odległości.
spanning: Podgraf jest rozpinany, gdy zawiera wszystkie wierzchołki danego grafu. Do ważnych przypadków należą drzewa rozpinające , podgrafy rozpinające będące drzewami oraz doskonałe dopasowania , obejmujące podgrafy, które są dopasowaniami. Podgraf rozpinający można również nazwać czynnikiem , zwłaszcza (ale nie tylko), gdy jest regularny.
rzadki: Graf rzadki to taki, który ma niewiele krawędzi w stosunku do liczby wierzchołków. W niektórych definicjach ta sama właściwość powinna być również prawdziwa dla wszystkich podgrafów danego grafu.
widmo
widmowe: Widmo wykresu to zbiór wartości własnych jego macierzy sąsiedztwa. Teoria grafów widmowych jest gałęzią teorii grafów, która wykorzystuje widma do analizy grafów. Zobacz także spektralne ekspansja .
podział: 1. Graf podzielony to graf, którego wierzchołki można podzielić na klikę i zbiór niezależny. Pokrewna klasa grafów, grafy z podwójnym podziałem, jest używana w dowodzie twierdzenia o silnym grafie doskonałym.; 2. Podział dowolnego grafu to podział jego wierzchołków na dwa niepuste podzbiory w taki sposób, że krawędzie obejmujące ten przekrój tworzą kompletny podgraf dwudzielny. Podziały grafu można przedstawić za pomocą struktury drzewiastej, zwanej rozkładem podziału . Rozłam nazywany jest silnym rozłamem, gdy nie jest przecinany przez żaden inny rozłam. Podział nazywamy nietrywialnym, gdy obie jego strony mają więcej niż jeden wierzchołek. Graf nazywamy pierwszym, gdy nie ma nietrywialnych podziałów.
kwadrat: 1. Kwadrat wykresu $G$ to potęga wykresu $G 2$ ; w przeciwnym kierunku $G$ jest pierwiastkiem kwadratowym z $G 2$ . Półkwadrat grafu dwudzielnego jest podwykresem jego kwadratu indukowanym przez jedną stronę dwudzielnego podziału.; 2. Wykres kwadratowy jest grafem planarnym, który można narysować w taki sposób, że wszystkie ograniczone ściany są 4-cyklami, a wszystkie wierzchołki stopnia ≤ 3 należą do zewnętrznej ściany.; 3. Kwadratowy wykres siatkowy to wykres kratowy zdefiniowany na podstawie punktów na płaszczyźnie o współrzędnych całkowitych połączonych krawędziami o jednostkowej długości.
stabilny: Zbiór stabilny jest synonimem zbioru niezależnego .
gwiazda: Gwiazda to drzewo z jednym wewnętrznym wierzchołkiem ; równoważnie jest to pełny graf dwudzielny $K 1, n$ dla pewnego $n \geq 2$ . Szczególny przypadek gwiazdy z trzema liśćmi nazywa się pazurem.
siła: Siła grafu jest minimalnym stosunkiem liczby krawędzi usuniętych z grafu do utworzonych składowych, do wszystkich możliwych usunięć; jest to analogiczne do twardości, opartej na usuwaniu wierzchołków.
silny: 1. Aby uzyskać informacje o silnej łączności i silnie połączonych składnikach grafów skierowanych, zobacz połączone i składowe . Silna orientacja to orientacja silnie powiązana; patrz orientacja .; 2. Dla mocne twierdzenie o doskonałym grafie , patrz doskonały .; 3. Graf silnie regularny to graf regularny, w którym każde dwa sąsiednie wierzchołki mają taką samą liczbę wspólnych sąsiadów, a każde dwa nieprzylegające wierzchołki mają taką samą liczbę wspólnych sąsiadów.; 4. Graf silnie akordowy to graf akordowy, w którym każdy parzysty cykl o długości sześciu lub więcej ma akord nieparzysty.; 5. Grafem silnie doskonałym jest graf, w którym każdy podgraf indukowany ma niezależny zbiór spełniający wszystkie maksymalne kliki. Grafy Meyniela są również nazywane „grafami bardzo silnie doskonałymi”, ponieważ w nich każdy wierzchołek należy do takiego niezależnego zbioru.
subforest: Podgraf lasu .
podgraf: Podgraf grafu $G$ to inny graf utworzony z podzbioru wierzchołków i krawędzi grafu $G$ . Podzbiór wierzchołków musi zawierać wszystkie punkty końcowe podzbioru krawędzi, ale może również zawierać dodatkowe wierzchołki. Podgraf rozpinający to taki, który zawiera wszystkie wierzchołki grafu; podgraf indukowany to taki, który zawiera wszystkie krawędzie, których punkty końcowe należą do podzbioru wierzchołków.
poddrzewo: Poddrzewo to spójny podgraf drzewa. Czasami, dla drzew ukorzenionych, poddrzewa są definiowane jako specjalny rodzaj połączonego podgrafu, utworzonego przez wszystkie wierzchołki i krawędzie osiągalne z wybranego wierzchołka.
następca: Wierzchołek następujący po danym wierzchołku na ścieżce skierowanej .
superkoncentrator: Superkoncentrator to graf z dwoma wyznaczonymi i równej wielkości podzbiorami wierzchołków $I$ i $O$ , tak że dla każdych dwóch równych podzbiorów $S$ z $I$ i $T$ $O$ istnieje rodzina rozłącznych ścieżek łączących każdy wierzchołek w $S$ z wierzchołkiem w $T$ . Niektóre źródła wymagają dodatkowo, aby superkoncentrator był skierowanym grafem acyklicznym, z $I$ jako jego źródłami i $O$ jako jego pochłaniaczami.
supergraf: Graf utworzony przez dodanie wierzchołków, krawędzi lub obu tych elementów do danego grafu. Jeśli $H$ jest podgrafem $G$ , to $G$ jest supergrafem $H$ .

T

theta: 1. Graf theta to suma trzech wewnętrznie rozłącznych (prostych) ścieżek, które mają te same dwa różne wierzchołki końcowe.; 2. Graf teta zbioru punktów na płaszczyźnie euklidesowej konstruuje się, konstruując system stożków otaczających każdy punkt i dodając jedną krawędź każdego stożka, do punktu, którego rzut na środkowy promień stożka jest najmniejszy.; 3. Liczba Lovásza lub funkcja theta Lovásza wykresu jest niezmiennikiem wykresu związanym z liczbą klik i liczbą chromatyczną, który można obliczyć w czasie wielomianowym za pomocą programowania półokreślonego.
Wykres Thomsena: Wykres Thomsena to nazwa pełnego wykresu dwudzielnego ${\ Displaystyle K_ {3,3}}$ .
topologiczny: 1. Graf topologiczny jest reprezentacją wierzchołków i krawędzi grafu za pomocą punktów i krzywych na płaszczyźnie (niekoniecznie z pominięciem przecięć).; 2. Teoria grafów topologicznych zajmuje się badaniem osadzania grafów.; 3. Sortowanie topologiczne jest algorytmicznym problemem ułożenia skierowanego grafu acyklicznego w porządek topologiczny, sekwencję wierzchołków taką, że każda krawędź przechodzi od wcześniejszego wierzchołka do późniejszego wierzchołka w sekwencji.
totalnie rozłączony: Synonim bez krawędzi .
tour: Zamknięty szlak, spacer , który zaczyna się i kończy w tym samym wierzchołku i nie ma powtarzających się krawędzi. Trasy Eulera to wycieczki wykorzystujące wszystkie krawędzie grafu; zobacz Eulera .
turniej: Turniej _ jest orientacją pełnego wykresu; to znaczy jest to graf skierowany, w którym każde dwa wierzchołki są połączone dokładnie jedną skierowaną krawędzią (biegnącą tylko w jednym z dwóch kierunków między dwoma wierzchołkami).
identyfikowalny: Graf identyfikowalny to graf zawierający ścieżkę Hamiltona.
szlak: Spacer bez powtarzających się krawędzi .
przechodni: Mający do czynienia z właściwością przechodnią . Zamknięcie przechodnie danego grafu skierowanego to graf w tym samym zbiorze wierzchołków, który ma krawędź od jednego wierzchołka do drugiego, ilekroć oryginalny graf ma ścieżkę łączącą te same dwa wierzchołki. Przechodnia redukcja wykresu to minimalny graf mający to samo domknięcie przechodnie; skierowane grafy acykliczne mają unikalną redukcję przechodnią. Orientacja przechodnia to orientacja wykresu, który jest jego własnym zamknięciem przechodnim; istnieje tylko dla wykresów porównawczych .
transpozycja: Graf transpozycji danego grafu skierowanego jest grafem o tych samych wierzchołkach, z każdą krawędzią odwróconą w kierunku. Można to również nazwać odwrotnością lub odwrotnością wykresu.
drzewo: 1. Drzewo jest grafem nieskierowanym, który jest zarówno spójny, jak i acykliczny, lub grafem skierowanym, w którym istnieje unikalne przejście od jednego wierzchołka (korzenia drzewa) do wszystkich pozostałych wierzchołków.; 2. $K$ -drzewo jest grafem utworzonym przez sklejenie $(k + 1)$ -klik razem na wspólnych $k$ -klikach. Drzewo w zwykłym znaczeniu to $1$ -drzewo zgodnie z tą definicją.
dekompozycja drzewa: Dekompozycja drzewa grafu $G$ to drzewo, którego węzły są oznaczone zbiorami wierzchołków grafu $G$ ; te zestawy nazywane są torbami. Dla każdego wierzchołka $v$ worki zawierające $v$ muszą indukować poddrzewo drzewa, a dla każdej krawędzi $uv$ musi istnieć worek zawierający zarówno $u$ , jak i $v$ . Szerokość rozkładu drzewa jest o jeden mniejsza niż maksymalna liczba wierzchołków w dowolnym z jego worków; szerokość drzewa $G$ jest minimalną szerokością dowolnego rozkładu drzewa $G$ .
szerokość drzewa: Szerokość drzewa grafu $G$ jest minimalną szerokością rozkładu drzewa $G$ . Można $go również$ $zdefiniować$ w kategoriach liczby kliki akordowego zakończenia G , rzędu przystani G lub $rzędu$ jeżyn G.
trójkąt: Cykl o długości trzy w grafie. Graf bez trójkątów jest grafem nieskierowanym, który nie ma żadnych trójkątnych podgrafów.
trywialny: Graf trywialny to graf z 0 lub 1 wierzchołkami. Graf z 0 wierzchołkami jest również nazywany grafem zerowym .
Turán: 1. Pál Turán; 2. Graf Turána jest zrównoważonym kompletnym grafem wieloczęściowym.; 3. Twierdzenie Turána mówi, że grafy Turána mają największą liczbę krawędzi spośród wszystkich grafów bez klik danego rzędu.; 4. Problem fabryki cegieł Turana prosi o podanie minimalnej liczby przecięć na rysunku kompletnego grafu dwudzielnego.

u

nieskierowany: Graf nieskierowany to graf, w którym dwa punkty końcowe każdej krawędzi nie są od siebie odróżnione. Zobacz także reżyserowane i mieszane . W grafie mieszanym krawędź nieskierowana to znowu taka, w której punkty końcowe nie są od siebie odróżnione.
jednorodny: Hipergraf jest $k$ -jednolity, gdy wszystkie jego krawędzie mają $k$ punktów końcowych, a jednorodny, gdy jest $k$ -jednolity dla pewnego $k$ . Na przykład zwykłe wykresy są takie same jak $2$ -jednolite hipergrafy.
uniwersalny: 1. Graf uniwersalny to graf, który zawiera jako podgrafy wszystkie grafy z danej rodziny grafów lub wszystkie grafy o danym rozmiarze lub kolejności w ramach danej rodziny grafów.; 2. Wierzchołek uniwersalny (zwany także wierzchołkiem lub wierzchołkiem dominującym) to wierzchołek, który sąsiaduje z każdym innym wierzchołkiem grafu. Na przykład wykresy kołowe i połączone wykresy progowe zawsze mają uniwersalny wierzchołek.; 3. W logice grafów wierzchołek, który jest uniwersalnie kwantyfikowany w formule można nazwać wierzchołkiem uniwersalnym dla tej formuły.; graf Graf , którego wierzchołkom i krawędziom nie przypisano wagi s; przeciwieństwo wykresu ważonego .
nieważony
wykres użyteczności: Wykres użyteczności to nazwa pełnego wykresu dwudzielnego ${\ Displaystyle K_ {3,3}}$ .

V

V: Zobacz zbiór wierzchołków .
wartościowość: synonim stopnia .
wierzchołek: Wierzchołek (liczba mnoga wierzchołków) jest (wraz z krawędziami) jedną z dwóch podstawowych jednostek , z których zbudowane są grafy. Wierzchołki grafów są często uważane za obiekty atomowe, bez struktury wewnętrznej.
vertex cut
oddzielający zbiór: Zbiór wierzchołków , których usunięcie powoduje rozłączenie grafu . Cięcie z jednym wierzchołkiem nazywane jest punktem artykulacji lub wierzchołkiem cięcia .
zbiór wierzchołków: Zbiór wierzchołków danego grafu $G$ , czasami oznaczany jako $V (G)$ .
wierzchołki: Zobacz wierzchołek .
Vizing: 1. Vadim G. Vizing; 2. Twierdzenie Vizinga , że indeks chromatyczny jest co najwyżej o jeden większy niż maksymalny stopień.; 3. Hipoteza Vizinga o liczbie dominacji iloczynów kartezjańskich grafów.
objętość: Suma stopni zbioru wierzchołków.

W

$W$: Litera $W$ jest używana w zapisie wykresów kołowych i wykresów wiatraków . Notacja nie jest znormalizowana.
Wagner: 1. Klaus Wagner; 2. Graf Wagnera , drabina Möbiusa z ośmioma wierzchołkami.; 3. Twierdzenie Wagnera charakteryzujące grafy planarne za pomocą ich zabronionych drugorzędnych.; 4. Twierdzenie Wagnera charakteryzujące grafy bezmolowe $K 5 .$
spacer: Spacer to skończona lub nieskończona sekwencja krawędzie , które łączą sekwencję wierzchołków . Spacery są czasami nazywane łańcuchami . Spacer jest otwarty , jeśli jego pierwszy i ostatni wierzchołek są różne, a zamknięty , jeśli się powtarzają.
słabo spójny: Graf skierowany nazywamy słabo spójnym, jeśli zastąpienie wszystkich jego krawędzi skierowanych krawędziami nieskierowanymi daje graf spójny (nieskierowany).
waga: Wartość liczbowa przypisana jako etykieta do wierzchołka lub krawędzi grafu. Waga podgrafu jest sumą wag wierzchołków lub krawędzi w tym podgrafie.; graf Graf , którego wierzchołkom lub krawędziom przypisano wagę s. Graf ważony wierzchołkami ma wagi na swoich wierzchołkach, a graf ważony krawędziami ma wagi na krawędziach.
ważony
dobrze pokolorowany: Dobrze pokolorowany graf to graf, którego wszystkie zachłanne kolorowania używają tej samej liczby kolorów.
dobrze kryjący: A dobrze pokryty graf to graf, którego wszystkie maksymalne zbiory niezależne są tej samej wielkości.
koło: Wykres kołowy to graf utworzony przez dodanie uniwersalnego wierzchołka do prostego cyklu.
szerokość: 1. Synonim degeneracji .; 2. W przypadku innych niezmienników grafów, znanych jako szerokość, zobacz szerokość pasma , szerokość gałęzi , szerokość kliki , szerokość ścieżki i szerokość drzewa .; 3. Szerokość dekompozycji drzewa lub dekompozycji ścieżki jest o jeden mniejsza niż maksymalny rozmiar jednego z jej worków i może być wykorzystana do zdefiniowania szerokości drzewa i szerokości ścieżki.; 4. Szerokość skierowanego grafu acyklicznego jest maksymalną licznością antyłańcucha.
wiatrak: Graf wiatraka to suma zbioru klik, wszystkie tego samego rzędu, z jednym wspólnym wierzchołkiem należącym do wszystkich klik i wszystkimi innymi wierzchołkami i krawędziami odrębnymi.

Zobacz też