Słowniczek teorii grafów - Glossary of graph theory

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 ] jest indukowanym podwykresem grafu G dla podzbioru wierzchołków S .
Pierwszy symbol '
Główny symbol jest często używany do modyfikacji notację niezmienników wykresu tak, że odnosi się do wykresu liniowego zamiast danego wykresu. Na przykład α ( G ) jest liczbą niezależności grafu; α ′( G ) jest liczbą dopasowania grafu, która jest równa liczbie niezależności grafu liniowego. Podobnie, χ ( G ) jest liczbą chromatyczną grafu; χ  ′( G ) to indeks chromatyczny wykresu, który jest równy liczbie chromatycznej wykresu liniowego.

A

absorbujący
Zbiór absorbujący grafu skierowanego to zbiór wierzchołków taki, że dla każdego wierzchołka istnieje krawędź od w kierunku wierzchołka .
achromatyczny
Liczba achromatyczna wykresu to maksymalna liczba kolorów w pełnej kolorystyce.
acykliczny
1. Wykres jest acykliczny, jeśli nie ma cykli. Nieskierowany graf acykliczny to to samo, co las . Skierowane grafy acykliczne rzadziej nazywane są acyklicznymi grafami skierowanymi.
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 wykresu jest macierzą, której rzędy i kolumny zarówno indeksowane wierzchołków grafu, z jednego w komórce dla rzędu I i kolumny j , kiedy wierzchołki I i J sąsiadują ze sobą, a zero inaczej.
przylegający
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 grafu G , α ( G ) (używając greckiej litery alpha) jest jego liczbą niezależności (patrz Independent ), a α ′( G ) jest liczbą dopasowania (patrz dopasowanie ).
zmienny
W grafie z dopasowaniem ścieżka przemienna jest ścieżką, której krawędzie występują naprzemiennie między dopasowanymi i niedopasowanymi krawędziami. Podobnie cykl naprzemienny jest cyklem, którego krawędzie występują naprzemiennie między dopasowanymi i niedopasowanymi krawędziami. Ścieżka rozszerzająca to ścieżka naprzemienna, która zaczyna się i kończy na nienasyconych wierzchołkach. Większe dopasowanie można znaleźć jako symetryczną różnicę dopasowania i ścieżki rozszerzającej; dopasowanie jest maksymalne wtedy i tylko wtedy, gdy nie ma ścieżki rozszerzającej.
antyłańcuchowy
W skierowanym grafie acyklicznym podzbiór S wierzchołków, które są nieporównywalne parami, tj. dla dowolnego w S nie ma skierowanej ścieżki z x do y lub z y do x . Zainspirowany pojęciem antyłańcuchów w częściowo uporządkowanych zestawach .
antykrawędziowy
Synonim non-edge , para nieprzyległych wierzchołków.
antytrójkąt
Zbiór niezależny od trzech wierzchołków, dopełnienie trójkąta.
wierzchołek
1. Wykres wierzchołkowy to wykres, w którym jeden wierzchołek można usunąć, pozostawiając podgraf planarny. Usunięty wierzchołek nazywa się wierzchołkiem. K -apex wykres przedstawia wykres, który może być płaski przez usunięcie k wierzchołków.
2. Synonim uniwersalnego wierzchołka , wierzchołek sąsiadujący ze wszystkimi innymi wierzchołkami.
drzewostan
Synonim drzewa ukorzenionego i skierowanego; zobacz drzewo .
łuk
Zobacz krawędź .
strzałka
Uporządkowane pary z wierzchołków , takim jak krawędź w skierowanej wykresie . Strzałka ( x , y ) ma ogon x , główkę y i kierunek od x do y ; Y jest uważany za bezpośredni następca do x i x bezpośredniego poprzednika do y . Strzałka ( y , x ) to odwrócona strzałka strzałki ( x , y ) .
punkt artykulacji
Wierzchołek w połączonym wykresie których usunięcie by odłączyć wykres.
-ary
K -ary drzewo jest zakorzenione drzewo, w którym każdy wierzchołek wewnętrzny ma nie więcej niż k dzieci. Jednoarkowe drzewo to tylko ścieżka. Drzewo dwuargumentowe jest również nazywane drzewem binarnym , chociaż termin ten bardziej poprawnie odnosi się do drzew dwuargumentowych , w których dzieci każdego węzła są rozróżniane jako lewe lub prawe dzieci (co najwyżej jedno z każdego typu). O drzewie k- arnym mówimy, że jest kompletne, jeśli każdy wewnętrzny wierzchołek ma dokładnie k dzieci.
powiększanie
Specjalny rodzaj ścieżki naprzemiennej; patrz na przemian .
automorfizm
Wykres automorfizmem jest symetrii wykresu izomorfizmem z wykresu na siebie.

b

torba
Jeden ze zbiorów wierzchołków w dekompozycji drzewa .
zrównoważony
Wykres dwudzielny lub wieloczęściowy jest zrównoważony, jeśli każdy z dwóch podzbiorów jego podziału wierzchołków ma rozmiary mieszczące się w sobie nawzajem.
przepustowość łącza
Pasma grafu G jest minimalne w stosunku do wszystkich uporządkowania wierzchołków G , długości najdłuższej krawędzi (liczby etapów w kolejności pomiędzy dwoma punktami końcowymi). Jest to również o jeden mniej niż rozmiar maksymalnej kliki w prawidłowym dopełnieniu interwału G , wybrany tak, aby zminimalizować rozmiar kliki.
bicykl
Synonim pełnego dwudzielnego grafu lub pełnego dwudzielnego podgrafu; zobacz kompletne .
dwojaki
Zwykle jest synonimem dla 2 -vertex-connected , ale czasami zawiera K 2, chociaż nie jest 2-connected. Zobacz połączone ; w przypadku elementów podwójnie połączonych patrz element .
numer wiążący
Najmniejszy możliwy stosunek liczby sąsiadów odpowiedniego podzbioru wierzchołków do rozmiaru podzbioru.
dwustronny
Dwudzielny wykres przedstawia wykres, którego wierzchołki mogą być podzielone na dwie rozłączne zbiory, tak że wierzchołki jednego zestawu nie są ze sobą połączone, ale mogą być połączone do wierzchołków 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. Wykresy dwudzielne są często zapisywane G = ( U , V , E ) gdzie U i V są podzbiorami wierzchołków każdego koloru. Jeśli jednak wykres nie jest połączony, może nie mieć unikalnego dwukolorowania.
biregularny
Biregularna wykres jest dwudzielna wykres, w którym znajdują się tylko dwa różne stopnie wierzchołków, po jednym dla każdego zestawu części bipartition wierzchołków.
blok
1. Blok grafu G jest podgrafem maksymalnym, który jest albo izolowanym wierzchołkiem, krawędzią mostka, albo podgrafem dwuspójnym. Jeśli blok jest połączony 2, każda para wierzchołków w nim należy do wspólnego cyklu. Każda krawędź wykresu należy dokładnie do jednego bloku.
2. Graf blokowy grafu G to inny graf, którego wierzchołkami są bloki G , z krawędzią łączącą dwa wierzchołki, gdy odpowiadające im bloki mają wspólny punkt artykulacji; to znaczy jest to wykres przecięcia bloków G . Wykres blokowy dowolnego wykresu to las .
3. Blok cięcia (lub bloków wartości odcięcia) wykres wykres G jest dwudzielny wykres gdzie PARTITE zestaw składa się z Cut-wierzchołków G , a drugi wierzchołek dla każdego bloku z G . Gdy G jest połączony, jego wykres punktu podziału blokowego jest drzewem.
4. Graf blokowy (zwany także drzewem klikowym, jeśli jest połączony, a czasem błędnie nazywanym drzewem Husimi) to graf, którego wszystkie bloki są grafami kompletnymi. Las wykres 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 wykresu.
obligacja
Minimalne cięcia zestaw : zestaw krawędzi których usunięcie odłącza wykres, dla którego nie jest podzbiorem ma te same własnoś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. Inny typ grafu, zwany także książką lub czworokątną księgą, to zbiór 4 cykli połączonych wspólnym brzegiem; iloczyn kartezjański gwiazdy z krawędzią.
3. Osadzenie księgi to osadzenie grafu w księdze topologicznej, przestrzeni utworzonej przez połączenie zbioru półpłaszczyzn wzdłuż wspólnej linii. Zwykle wierzchołki osadzenia muszą znajdować się na linii zwanej grzbietem osadzenia, a krawędzie osadzenia muszą leżeć w jednej półpłaszczyźnie, jednej ze stron książki.
cierń
Jeżyny jest zbiorem połączonych wzajemnie stykającymi subgraphs, gdzie dwa subgraphs dotykowego, dzielą wierzchołek lub każdy zawiera jeden 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 to maksymalny rząd którejkolwiek z jego jeżyn.
rozkład-gałęzi
Oddział-rozkładu od G jest hierarchiczne grupowanie krawędzi G , reprezentowanej przez Nieukorzenione binarnego drzewa z jego liści oznaczonych przez krawędzie G . Szerokość rozkładu gałęzi to maksymalna, ponad krawędziami e tego drzewa binarnego, liczba wspólnych wierzchołków między podgrafami, określona przez krawędzie G w dwóch poddrzewach rozdzielonych przez e . Branchwidth z G jest minimalna szerokość każdym rozgałęzieniu rozkładu G .
szerokość oddziału
Zobacz rozkład gałęzi .
most
1. Mostek , przesmyk lub krawędź cięcia to krawędź, której usunięcie spowodowałoby rozłączenie wykresu. Graf bez mostków to taki, który nie ma mostków; równoważnie graf dwukrawędziowy.
2. Zwłaszcza w kontekście testowania płaskości , mostek cyklu jest maksymalnym podgrafem, który jest rozłączny od cyklu i w którym każde dwie krawędzie należą do ścieżki wewnętrznie rozłącznej od cyklu. Akord to jednokrawędziowy most. Cykl obwodowa jest cykl o co najwyżej jeden mostek; musi to być ściana w każdym płaskim osadzeniu jego wykresu.
3. Most 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. Zmostkowany wykres przedstawia wykres, w którym w każdym cyklu z czterech lub większej liczby wierzchołków znajduje się mostek.
bez mostka
Wykres bezmostkowego jest wykresem, który ma krawędzie mostków; czyli graf dwukrawędziowy .
motyl
1. Wykres motyla ma pięć wierzchołków i sześć krawędzi; tworzą go dwa trójkąty, które mają wspólny wierzchołek.
2. Sieć motylkowa to graf używany jako architektura sieci w obliczeniach rozproszonych, ściśle powiązany z cyklami połączonymi kostkami .

C

C
C n jest n- wierzchołkowym wykresem cyklu ; zobacz cykl .
kaktus
Wykres kaktus , drzewo kaktus, kaktus, lub Husimi drzewa jest połączony wykres, w którym każda krawędź należy do co najwyżej 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, nazywa się go świątecznym kaktusem.
klatka szybowa
Klatka jest regularny wykres z najmniejszym możliwym, aby jego obwodu.
kanoniczny
kanonizacja
Postaci kanonicznej wykresu jest niezmienna, tak że dwa wykresy równych niezmienników wtedy i tylko wtedy, gdy są izomorficzne. Formy kanoniczne mogą być również nazywane niezmiennikami kanonicznymi lub niezmiennikami zupełnymi i są czasami definiowane tylko dla grafów w obrębie określonej rodziny grafów. Kanonizacja grafu to proces obliczania formy kanonicznej.
karta
Wykres utworzony z danego grafu przez usunięcie jednego wierzchołka, zwłaszcza w kontekście przypuszczenia rekonstrukcji . Zobacz także deck , multiset wszystkich kart grafu.
szerokość rzeźbienia
Carving width to pojęcie szerokości wykresu analogiczne do branchwidth, ale wykorzystujące hierarchiczne grupowanie wierzchołków zamiast hierarchicznego grupowania krawędzi.
gąsienica
Drzewa gąsienica lub gąsienica jest drzewem, w którym wewnętrzne węzły wywołać drogę.
środek
Centrum wykresu jest zbiór wierzchołków co najmniej mimośród .
łańcuch
1. Synonim spaceru .
2. Stosując metody z topologii algebraicznej do grafów, element kompleksu łańcuchowego , czyli zbiór wierzchołków lub zbiór krawędzi.
Stała Cheegera
Zobacz rozszerzenie .
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 jej indeks chromatyczny; zobacz chromatyczne i kolorowanie .
dziecko
W ukorzenionym drzewie dziecko wierzchołka v jest sąsiadem v wzdłuż wychodzącej krawędzi, która jest odwrócona od korzenia.
akord
akordowy
1. Akord cyklu to krawędź, która nie należy do cyklu, dla której oba punkty końcowe należą do cyklu.
2. Wykres akordowy to wykres, 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ść lub więcej ma nieparzysty akord.
4. Dwudzielny graf akordowy nie jest akordowy (chyba, że ​​jest lasem); jest to wykres 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 skrzyżowanie z kolekcji akordów nazywa się wykres krąg .
chromatyczny
Mając do czynienia z kolorowaniem; zobacz kolor . Teoria grafów chromatycznych to teoria kolorowania grafów. Liczba chromatyczna χ ( G ) jest minimalną liczbą potrzebnych kolorów odpowiedniego zabarwienia G . χ  '( G ) jest chromatycznej wskaźnik z G , minimalną liczbą potrzebnych kolorów w odpowiedniej krawędzi farbowania z G .
do wyboru
możliwość wyboru
Wykres jest k -wybieralny, jeśli ma kolorowanie listy, gdy każdy wierzchołek ma listę k dostępnych kolorów. Wybieralność grafu to najmniejsze k, dla którego k jest do wyboru.
okrąg
Wykres koło jest wykresem przecięcia z cięciwy okręgu.
okrążenie
Obwód może odnosić się do zamkniętego szlaku lub elementu przestrzeni rowerowej (podgraf Eulera). Ranking Obwód grafu jest wymiarem jego przestrzeni cyklu.
obwód
Obwód wykresu jest najdłuższa długość prostego cyklu. Wykres jest hamiltonianem 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 definiowany jako grafy posiadające określoną właściwość. Słowo „klasa” jest używane zamiast „zbiór”, ponieważ o ile nie zostaną wprowadzone specjalne ograniczenia (takie jak ograniczenie wierzchołków, które mają być rysowane z określonego zestawu, i zdefiniowanie krawędzi jako zestawów dwóch wierzchołków), klasy grafów zwykle nie są zestawami po sformalizowaniu za pomocą teorii mnogości.
2. Klasa kolorów grafu kolorowego to zbiór wierzchołków lub krawędzi o jednym określonym kolorze.
3. W kontekście twierdzenia Vizinga , o kolorowaniu prostych grafów krawędziowych, mówi się, że graf należy do klasy pierwszej, jeśli jego indeks chromatyczny jest równy maksymalnemu stopniowi, i 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 drugiej.
pazur
Pazur jest drzewo jeden wewnętrzny wierzchołek oraz trzech liści, lub równoważnie całkowitego dwuczęściowego wykresie K 1,3 . Pazur wolne wykres jest wykresem, który nie indukowanej podgrafu który jest pazur.
klika
Klika to zestaw wzajemnie sąsiednich wierzchołków (lub pełna subgraph wywołane tym zestawie). Czasami klika jest definiowana 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 -clique jest klika z rzędu k . Liczba kliki κ ( G ) grafu G jest rzędem największej kliki. Wykres klika jest wykresem przecięcia maksymalnej klik. Zobacz także biclique , kompletny dwudzielny podgraf.
drzewo klikowe
Synonim grafu blokowego .
szerokość kliku
Klika szerokości grafu G jest minimalna liczba odrębnych etykiety niezbędne do skonstruowania G przez operacje, które tworzą znakowanego wierzchołka tworzą rozłączne związek dwóch znakowanych wykresach dodać krawędź łączącą wszystkie pary wierzchołków o podanym etykiet lub znakowaniu plików wszystkie wierzchołki z daną etykietą. Wykresy szerokości kliki co najwyżej 2 to dokładnie wykresy .
Zamknięte
1. Zamknięte sąsiedztwo to takie, które obejmuje swój centralny wierzchołek; zobacz sąsiedztwo .
2. Spacer zamknięty to taki, który zaczyna się i kończy na tym samym wierzchołku; zobacz spacer .
3. Graf jest domknięty przechodnie, jeśli równa się jego własnemu domknięciu przechodniemu; zobacz przechodnie .
4. Własność grafu jest zamykana w ramach jakiejś operacji na grafach, jeśli, ilekroć argument lub argumenty operacji mają tę właściwość, to wynik jest taki sam. Na przykład własności dziedziczne są zamknięte pod podgrafami indukowanymi; właściwości monotoniczne są zamknięte pod podgrafami; i małoletnie zamknięte nieruchomości są zamknięte dla nieletnich.
zamknięcie
1. Dla przechodniego domknięcia grafu skierowanego zobacz przechodnie .
2. Domknięcie grafu skierowanego to zbiór wierzchołków, które nie mają krawędzi wychodzących do wierzchołków poza domknięciem. Na przykład zlew to zamknięcie z jednym wierzchołkiem. Problemem zamknięcie jest problem znalezienia zamknięcie minimalnej lub maksymalnej wagi.
współ-
Ten przedrostek ma różne znaczenia, zwykle związane z grafami dopełnień . Na przykład cograph jest wykresem utworzonym przez operacje, które zawierają komplementację; cocoloring się zabarwienie, w którym każdy indukuje wierzchołków albo niezależny zestaw (jak w odpowiednie kolorowanie) lub klika (jak w zabarwieniu dopełniacza).
kolor
kolorowanie
1. Kolorowanie grafu to oznaczanie 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żda jest skojarzona z jednym z kolorów.
2. Niektórzy autorzy posługują się „kolorystowaniem”, bez zastrzeżeń, w znaczeniu właściwego kolorowania, takiego, które przyporządkowuje różne kolory punktom końcowym każdej krawędzi. W kolorowaniu wykresó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że być pokolorowany co najwyżej czterema kolorami. Mówi się, że wykres jest k -kolorowy, jeśli został (odpowiednio) pokolorowany k kolorów, a k -kolorowy lub k -chromatyczny, jeśli jest to możliwe.
3. Zbadano wiele odmian kolorowania, w tym kolorowanie krawędzi (kolorowanie krawędzi w taki sposób, aby żadne dwie krawędzie o tym samym punkcie końcowym nie miały wspólnego koloru), kolorowanie list (właściwe kolorowanie każdego wierzchołka ograniczonego do podzbioru dostępnych kolorów), kolorowanie acykliczne (każdy dwukolorowy podgraf jest acykliczny), współkolorowanie (każda klasa koloru indukuje niezależny zbiór lub klikę), pełne kolorowanie (każde dwie klasy kolorów mają wspólną krawędź) i całkowite kolorowanie (zarówno krawędzie, jak i wierzchołki są kolorowe).
4. Numer kolorowania grafu to jeden plus degeneracja . Nazywa się to tak, ponieważ zastosowanie algorytmu zachłannego kolorowania do porządku 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 kolejności częściowej. 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 rzędu częściowego.
komplement
Wykres dopełniacza wykresu prostej G jest kolejnym wykresem tego samego zestawu wierzchołek jako G , przy krawędzi na każde dwa wierzchołki, które nie sąsiadują z G .
kompletny
1. Kompletny graf to taki, w którym co dwa wierzchołki sąsiadują ze sobą: obecne są wszystkie krawędzie, które mogą istnieć. Kompletny wykres z n wierzchołkami jest często oznaczany K n . Zakończeniu dwustronnego wykresu jest taki, w którym co dwa wierzchołki po przeciwnych stronach przegrody wierzchołki są obok siebie. Kompletny graf dwudzielny z wierzchołkami a po jednej stronie przegrody 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 wieloczęściowe, grafy , w których wierzchołki są podzielone na więcej niż dwa podzbiory, a każda para wierzchołków w różnych podzbiorach sąsiaduje ze sobą; jeśli liczby wierzchołków w podzbiorach to a , b , c , ... to ten wykres oznaczymy K a , b , c , ... .
2. Uzupełnieniem danego grafu jest supergraf, który ma jakąś pożądaną właściwość. Na przykład uzupełnienie akordowe jest supergrafem, który jest grafem akordowym.
3. Pełne dopasowanie jest synonimem idealnego dopasowania ; zobacz dopasowywanie .
4. Kolorystyka pełna to kolorystyka właściwa, w której każda para kolorów jest używana dla punktów końcowych przynajmniej jednej krawędzi. Każda kolorystyka z minimalną liczbą kolorów jest kompletna, ale mogą istnieć kompletne kolorystyki z większą liczbą kolorów. Liczba achromatyczna wykresu to maksymalna liczba kolorów w pełnej kolorystyce.
5. Kompletny niezmiennik grafu jest synonimem formy kanonicznej, niezmiennikiem, który ma różne wartości dla grafów nieizomorficznych.
składnik
Podłączone urządzenie wykresu jest ilość połączone subgraph. Termin ten jest również używany dla maksymalnych podgrafów lub podzbiorów wierzchołków grafu, które mają jakiś wyższy poziom łączności, w tym elementy dwuspójne , trójpołączone elementy i silnie połączone elementy .
kondensacja
Kondensacji ukierunkowanej wykresie G jest kierowany acykliczny wykres z jednego wierzchołka dla każdego składnika silnie połączony z G i na krawędzi łączącej pary elementów, które zawierają dwa punkty końcowe co najmniej jednej krawędzi, G .
stożek
Wykres zawierający uniwersalny wierzchołek .
łączyć
Przyczyna do podłączenia .
połączony
Połączone wykresu jest taki, w którym każda para wierzchołków tworzy punkty końcowe drogi. Wyższe formy spójności obejmują silną spójność 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 może rozłączyć grafu) i k -krawędź -połączone grafy (usunięcie mniej niż k krawędzi nie może rozłączyć grafu).
rozmawiać
Graf odwrotny jest synonimem grafu transponowanego; zobacz transponować .
rdzeń
1. Rdzeń k jest indukowanym podgrafem utworzonym przez usunięcie wszystkich wierzchołków o stopniu mniejszym 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 od G do samego siebie jest izomorfizmem.
3. Rdzeń grafu G jest grafem minimalnym H takim, że istnieją homomorfizmy od G do H i odwrotnie. H jest unikalny aż do izomorfizmu. Może być reprezentowany jako indukowany podgraf G i jest rdzeniem w tym sensie, że wszystkie jego autohomomorfizmy są izomorfizmami.
4. W teorii dopasowań grafów rdzeń grafu jest aspektem jego dekompozycji Dulmage-Mendelsohna , utworzonej jako suma wszystkich maksymalnych dopasowań.
cotree
1. Dopełnienie drzewa opinającego .
2. Ukorzeniona struktura drzewa używana do opisania kografu , w której każdy wierzchołek kopuły jest liściem drzewa, każdy wewnętrzny węzeł drzewa jest oznaczony jako 0 lub 1, a dwa wierzchołki kopuły sąsiadują ze sobą wtedy i tylko wtedy, gdy ich najniższy wspólny przodek w drzewie jest oznaczony jako 1.
okładka
Pokrywa wierzchołek jest zbiór wierzchołków wypadku każdej krawędzi, w postaci wykresu. Pokrywa krawędź jest zestaw krawędzi wypadku do każdego wierzchołka na wykresie. Zbiór podwykresów grafu pokrywa ten graf, jeśli jego suma – wzięta w kierunku wierzchołkowym i krawędziowym – jest równa grafowi.
krytyczny
Graf krytyczny dla danej właściwości to graf, który ma tę właściwość, ale taki, że każdy podgraf utworzony przez usunięcie pojedynczego wierzchołka nie ma tej właściwości. Na przykład wykres czynnik krytyczny to taki, który ma idealne dopasowanie (1 czynnik) dla każdego usunięcia wierzchołka, 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 każde usunięcie jednego wierzchołka.
sześcian
sześcienny
1.   Wykres sześcienny , ośmiowierzchołkowy wykres wierzchołków i krawędzi sześcianu.
2.   Graf hipersześcianowy , wyższe uogólnienie grafu sześciennego.
3.   Wykres sześcienny złożony , utworzony z hipersześcianu przez dodanie pasujących łączących przeciwległych wierzchołków.
4.   Wykres sześcienny podzielony na pół, półkwadrat grafu hipersześcianowego.
5.   Sześcian częściowy , podgraf zachowujący odległość 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 krawędzie padające.
8.   Cykle połączone sześcianami , graf sześcienny utworzony przez zastąpienie każdego wierzchołka hipersześcianu przez cykl.
skaleczenie
zestaw cięty
Cięcia jest podział wierzchołków grafu na dwa podzbiory, lub zestaw (znany również jako wycięcie Set) krawędzi, które rozciągają się tak partycji, jeżeli ten zestaw jest niepusty. Mówi się, że krawędź obejmuje partycję, jeśli ma punkty końcowe w obu podzbiorach. W ten sposób usunięcie wyciętego zbioru z połączonego wykresu powoduje jego rozłączenie.
punkt cięcia
Zobacz punkt artykulacji .
wyciąć przestrzeń
Przestrzeń cięcia grafu to GF(2) - przestrzeń wektorowa , której elementami są wycięty zbiór s grafu, a jako operacja dodawania wektorów symetryczna różnica zbiorów.
cykl
Cyklu może być albo znajduje się w zamkniętym odległości (zwany również turystycznej ), lub bardziej konkretnie do zamkniętego bez powtarzanych odległości wierzchołków, a tym samym krawędzi (zwany również prosty cykl). W obu przypadkach wybór pierwszego wierzchołka jest zwykle uważany za nieistotny: cykliczne permutacje spaceru dają ten sam cykl. Ważnymi szczególnymi przypadkami cykli są cykle hamiltonowskie , indukowane , peryferyjne oraz najkrótszy cykl, który określa obwód wykresu. Cykl k jest cyklem o długości k ; na przykład 2- cykl to dwukąt, a 3- cykl to trójkąt. Wykres cyklu jest wykresem, który sam jest prosty pierścień; wykres cyklu z n wierzchołkami jest powszechnie oznaczany jako C n . Przestrzeń cyklu to przestrzeń wektorowa generowana przez proste cykle na grafie.

D

DAG
Skrót od skierowanego grafu acyklicznego , skierowanego grafu bez żadnych skierowanych cykli.
pokład
Multizbiór grafów utworzony z pojedynczego grafu G poprzez usunięcie pojedynczego wierzchołka na wszystkie możliwe sposoby, szczególnie w kontekście przypuszczenia rekonstrukcji . Poszycie krawędziowe tworzy się w ten sam sposób, usuwając pojedynczą krawędź na wszystkie możliwe sposoby. Wykresy w talii są również nazywane kartami . Zobacz także krytyczne (wykresy, które mają właściwość, której nie ma żadna karta) i hipo- (wykresy, które nie mają właściwości, której nie posiadają wszystkie karty).
rozkład
Zobacz rozkład drzewo , rozkład ścieżek lub branżowych rozkładowi .
zdegenerowany
degeneracja
K wykres -degenerate jest nieukierunkowane wykres, w którym każdy wywołane subgraph ma minimalny stopień co najwyżej k . Degeneracja wykresu jest najmniejszym k , dla których jest to k -degenerate. Kolejność degeneracji jest porządkowaniem wierzchołków tak, że każdy wierzchołek ma minimalny stopień w indukowanym podgrafie i wszystkich późniejszych wierzchołkach; w porządku degeneracyjnym k- degenerowanego grafu każdy wierzchołek ma co najwyżej k późniejszych sąsiadów. Degeneracja jest również znana jako liczba k- rdzeń, szerokość i powiązanie, a jedna plus degeneracja jest również nazywana liczbą kolorowania lub liczbą Szekeresa-Wilfa. k -degenerate wykresy zostały również nazywany k -inductive wykresy.
stopień
1. Stopień wierzchołka grafu to liczba krawędzi padających. Stopień grafu G (lub jego maksymalny stopień) to maksimum stopni jego wierzchołków, często oznaczanych jako Δ( G ) ; minimalny stopień G jest minimalnym stopniem jego wierzchołków, często oznaczanym jako δ ( G ) . Stopień jest czasami nazywany wartościowością ; stopień v w G może być oznaczony jako d G ( v ) , d ( G ) lub deg ( v ) . Całkowity stopień to suma stopni wszystkich wierzchołków; według lematu uzgadniania jest to liczba parzysta. Sekwencja stopni jest zbiór stopni wszystkich wierzchołków w uporządkowanej kolejności od największej do najmniejszej. 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 minor.
Δ, δ
Δ( G ) (używając greckiej litery delta) jest maksymalnym stopniem wierzchołka w G , a δ ( G ) jest minimalnym stopniem; zobacz stopień .
gęstość
W grafie n węzłów gęstość jest stosunkiem liczby krawędzi grafu do liczby krawędzi w pełnym grafie na 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 z sąsiednich węzłów wynosi 1. Jest to poziom węzła minus jeden. Zauważ jednak, że niektórzy autorzy zamiast tego używają głębokości jako synonimu poziomu węzła.
średnica
Średnica grafu połączonego to maksymalna długość najkrótszej ścieżki . Oznacza to, że jest to maksymalna odległość między parami wierzchołków na wykresie. Jeśli graf ma wagi na swoich krawędziach, 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 jako liczbę krawędzi. W przypadku odłączonych wykresów definicje są różne: średnica może być zdefiniowana jako nieskończona, jako największa średnica połączonego komponentu lub może być niezdefiniowana.
diament
Wykres diament jest nieukierunkowane wykres z czterema wierzchołkami i pięciu krawędziach.
odłączony
Silne ly podłączony . (Nie mylić z rozłączonym )
digon
Digon jest prosty cykl długości dwa w ukierunkowanej wykresu lub multigraf. Digons nie mogą występować w prostych grafach nieskierowanych, ponieważ wymagają dwukrotnego powtórzenia tej samej krawędzi, co narusza definicję simple .
dwuznak
Synonim grafu skierowanego .
dipath
Zobacz skierowaną ścieżkę .
bezpośredni poprzednik
Ogon skierowanej krawędzi, której głowa jest danym wierzchołkiem.
bezpośredni następca
Głowa krawędzi skierowanej, której ogon jest danym wierzchołkiem.
skierowany
Skierowane wykresu jest taki, w którym krawędzie mają wybitną kierunku od jednego do drugiego wierzchołka. W grafie mieszanym krawędź skierowana to znowu taka, która ma wyraźny kierunek; skierowane krawędzie mogą być również nazywane łukami lub strzałkami.
skierowany łuk
Zobacz strzałkę .
skierowana krawędź
Zobacz strzałkę .
linia skierowana
Zobacz strzałkę .
skierowana ścieżka
Ścieżki , w którym wszystkie krawędzie y mają ten sam kierunek . Jeśli skierowany prowadzi ścieżka z wierzchołka x do wierzchołka y , x jest poprzednikiem na Y , Y jest następcą z X i Y jest uważany oddalone od x .
kierunek
1. Asymetryczna relacja między dwoma sąsiednimi wierzchołkami na wykresie , reprezentowana jako strzałka .
2. Asymetryczna relacja między dwoma wierzchołkami w ścieżce skierowanej .
rozłączyć się
Powód do odłączenia .
niepowiązany
Brak połączenia .
nieskładny
1. Dwa podgrafy są rozłączne krawędziowe, jeśli nie mają wspólnych krawędzi, a wierzchołki rozłączne, jeśli nie mają wspólnych wierzchołków.
2. Rozłączna suma dwóch lub więcej grafów to graf, którego zbiory wierzchołków i krawędzi są rozłącznymi sumami odpowiednich zbiorów.
dystans
Odległość między dwoma wierzchołkami na wykresie jest długością najkrótszej ścieżki posiadającej dwa wierzchołki jak swoich punktów końcowych.
domatyczny
Podział domatyczny grafu to podział wierzchołków na zbiory dominujące. Liczba Domatic wykresu jest maksymalna ilość zbiory dominuje w takiej strefie.
dominujący
Zbiór dominujący to zbiór wierzchołków, który zawiera lub sąsiaduje z każdym wierzchołkiem grafu; nie należy mylić z pokryciem wierzchołków, zbiorem wierzchołków, który występuje na wszystkich krawędziach grafu. Do ważnych specjalnych typów zbiorów dominujących należą zbiory niezależne dominujące (zbiory dominujące, które są również zbiorami niezależnymi) oraz zbiory dominujące połączone (zbiory dominujące, które indukują połączone podgrafy). Zbiór dominujący z jednym wierzchołkiem można również nazwać wierzchołkiem uniwersalnym. Liczba dominacji grafu to liczba wierzchołków w najmniejszym zbiorze dominującym.

mi

mi
E ( G ) to zbiór krawędzi G ; zobacz zestaw krawędzi .
ucho
Ucho grafu to ścieżka, której punkty końcowe mogą się pokrywać, ale w której poza tym nie ma powtórzeń wierzchołków ani krawędzi.
rozkład ucha
Rozkładu ucho jest podział krawędzi wykresu na sekwencję uszu, każdy z których punkty końcowe (po pierwszej) należą do poprzedniego ucha, a każdy z którego wnętrze punkty nie należą do żadnej wcześniejszej ucha. Otwarte ucho to prosta ścieżka (ucho bez powtarzających się wierzchołków), a otwarty rozkład ucha to rozkład ucha, w którym każde ucho po pierwszym jest otwarte; graf ma otwarty rozkład ucha wtedy i tylko wtedy, gdy jest dwupołączony. Ucho jest nieparzyste, jeśli ma nieparzystą liczbę krawędzi, a nieparzysty rozkład ucha to rozkład ucha, w którym każde ucho jest nieparzyste; wykres ma nieparzysty rozkład ucha wtedy i tylko wtedy, gdy jest czynnik krytyczny.
ekscentryczność
Ekscentryczność wierzchołka to najdalsza odległość od niego do dowolnego innego wierzchołka.
krawędź
Krawędź jest (razem z wierzchołkami) jedną z dwóch podstawowych jednostek, z których budowane są grafy. Każda krawędź ma dwa (lub w hipergrafach więcej) wierzchołki, do których jest dołączona, zwane jej punktami końcowymi. Krawędzie mogą być skierowane lub nieskierowane; krawędzie nieskierowane są również nazywane liniami, a krawędzie skierowane są również nazywane łukami lub strzałkami. W nieskierowanym prostym grafie krawędź może być reprezentowana jako zbiór jego wierzchołków, a w skierowanym prostym grafie może być reprezentowana jako uporządkowana para jego wierzchołków. Krawędź łącząca wierzchołki x i y jest czasami zapisywana jako xy .
krawędź cięcia
Zestaw z krawędzią y, którego usunięcie odłącza ten wykres . Cięcie na jednej krawędzi nazywane jest mostem , przesmykiem lub krawędzią cięcia .
zestaw krawędzi
Zbiór krawędzi danego grafu G , czasami oznaczany przez E ( G ) .
wykres bez krawędzi
Wykres bez krawędzi lub całkowicie odłączony wykres na dany zbiór wierzchołków jest wykresem, który nie posiada krawędzi. Czasami nazywa się go pustym wykresem, ale termin ten może również odnosić się do wykresu bez wierzchołków.
osadzanie
Wykres osadzanie jest topologiczna przedstawia wykres jako podzbiór przestrzeni topologicznej przy każdym wierzchołku reprezentowane jako punkt, każda krawędź reprezentowane przez krzywą o punktów końcowych krawędzi w końcowych krzywej, a nie inne przecięcia wierzchołków lub krawędzie. Płaska wykres jest wykresem, który ma takie osadzanie na płaszczyźnie euklidesowej i toroidalne wykres jest wykresem, który ma takie osadzanie na torusa. Do rodzaju wykresu jest minimalne możliwe rodzaj dwuwymiarowej kolektor , na którym może być osadzony.
pusty wykres
1. Graf bez krawędzi na niepustym zbiorze wierzchołków.
2. Wykres rzędu zero , wykres bez wierzchołków i krawędzi.
kończyć się
Koniec nieskończonej wykresie to równoważność klasy promieni, w których 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 nazywa się ogonem, a drugi punkt końcowy nazywa się głową .
wyliczenie
Enumeracja grafów to problem zliczania grafów w danej klasie grafów, w funkcji ich kolejności. Mówiąc bardziej ogólnie, problemy enumeracyjne mogą odnosić się albo do problemów z liczeniem pewnej klasy obiektów kombinatorycznych (takich jak kliki, niezależne zbiory, kolorowania lub drzewa opinające), albo do algorytmicznego wyliczania wszystkich takich obiektów.
Eulerian
Łańcuch Eulera znajduje się w odległości, która wykorzystuje każdą krawędź grafu dokładnie raz. Obwód Eulera (zwany również cyklem Eulera lub trasą Eulera) to zamknięty spacer, który wykorzystuje każdą krawędź dokładnie raz. Wykres Eulera to wykres, który ma obwód Eulera. W przypadku grafu nieskierowanego oznacza to, że graf jest połączony i każdy wierzchołek ma parzysty stopień. W przypadku grafu skierowanego oznacza to, że graf jest silnie powiązany i każdy wierzchołek ma stopień wejściowy równy stopniowi zewnętrznemu. W niektórych przypadkach wymagania dotyczące łączności są poluzowane, a wykres spełniający tylko wymagania stopnia jest nazywany Eulera.
parzysty
Podzielna przez dwa; na przykład cykl parzysty to cykl, którego długość jest parzysta.
ekspander
Wykres ekspandera wykres, którego ekspansja ekspansja wierzchołkiem lub krawędzią widmowej rozszerzalności jest ograniczony od zera.
ekspansja
1. Rozszerzenie krawędzi, liczba izoperymetryczna lub stała Cheegera grafu G jest minimalnym stosunkiem, w podzbiorach S co najwyżej połowy wierzchołków G , liczby krawędzi pozostawiających S do liczby wierzchołków w S .
2. Rozszerzenie wierzchołków, liczba izoperymetryczna wierzchołków lub powiększenie grafu G jest minimalnym stosunkiem w podzbiorach S co najwyżej połowy wierzchołków G , liczby wierzchołków na zewnątrz, ale sąsiadujących z S do liczby wierzchołków w S .
3. Unikalne rozwinięcie sąsiada grafu G jest minimalnym stosunkiem liczby wierzchołków poza S, ale sąsiadujących z unikalnym wierzchołkiem w S, do liczby wierzchołków w S , w podzbiorach co najwyżej połowy wierzchołków G .
4. Rozszerzenie widmowe d -grafu regularnego G jest przerwą widmową między największą wartością własną d jej macierzy sąsiedztwa a drugą co do wielkości wartością własną.
5. Rodzina grafów ma ekspansję ograniczoną, jeśli wszystkie jej r- płytkie drobne mniejsze mają stosunek krawędzi do wierzchołków ograniczony funkcją r , a rozwinięcie wielomianowe, jeśli funkcja r jest wielomianem.

F

Twarz
W grafie płaskim lub osadzeniu grafu połączony składnik podzbioru płaszczyzny lub powierzchni osadzenia, który jest odłączony od grafu. W przypadku osadzenia w płaszczyźnie wszystkie ściany oprócz jednej będą ograniczone; jedyną wyjątkową twarzą, która rozciąga się w nieskończoność, jest twarz zewnętrzna.
czynnik
Czynnikiem grafu jest podgraf spinający: podgraf, który zawiera wszystkie wierzchołki grafu. Termin ten jest używany przede wszystkim w kontekście regularnych podgrafów: współczynnik k jest współczynnikiem k regularnym. W szczególności współczynnik 1 jest tym samym, co idealne dopasowanie. Czynnik krytyczny wykres przedstawia wykres na którym usuwanie dowolny jeden wierzchołek tworzy wykres z 1 czynnika a.
faktoryzacja
Wykres faktoryzacji jest podział krawędzi wykresu na czynniki; k -factorization jest partycją na k -factors. Na przykład 1 -faktoryzacja to kolorowanie krawędzi z dodatkową właściwością, że każdy wierzchołek przylega do 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 wykresy są skończone, nie mówiąc tego wprost. Wykres jest lokalnie skończony, jeśli każdy wierzchołek ma skończoną liczbę krawędzi padających. 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.
Pierwsze zamówienie
Logika grafów pierwszego rzędu jest formą logiki, w której zmienne reprezentują wierzchołki grafu i istnieje predykat binarny do testowania, czy dwa wierzchołki sąsiadują ze sobą. Należy odróżnić od logiki drugiego rzędu, w której zmienne mogą również reprezentować zbiory wierzchołków lub krawędzi.
-klapka
Dla zbioru wierzchołków X , klapa X jest spójną składową podgrafu indukowanego utworzonego przez usunięcie X . Terminologia klap jest powszechnie używana w kontekście schronień , funkcji, które mapują małe zestawy wierzchołków do ich klap. Zobacz także mostek cyklu, który jest klapą wierzchołków cyklu lub akordem cyklu.
zabroniony
Zabronione charakterystyka wykres jest charakterystyka rodziny wykresach jako jest wykresy, które nie mają pewne inne wykresy jak subgraphs indukowanych subgraphs lub opieki. 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 zabronione.
Las
Las jest to wykres nieukierunkowane bez cykli (A suma rozłączna z nieukorzenionych drzew), albo skierowany wykres utworzony jako związek rozłącznego sadzonek drzew.
Frucht
1.   Robert Frucht
2. Wykres 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 indukowanego .
wykres funkcjonalny
Funkcjonalny wykres jest skierowany wykres, na którym każdy wierzchołek ma poza jeden stopień. Równoważnie graf funkcjonalny jest maksymalnie ukierunkowanym 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 .
geodezyjne
Jako rzeczownik, geodezja jest synonimem najkrótszej ścieżki . Kiedy jest używany jako przymiotnik, oznacza to, że odnosi się do najkrótszych ścieżek lub najkrótszych odległości ścieżek.
ogromny
W teorii grafów losowych składnik gigantyczny to połączony składnik, który zawiera stały ułamek wierzchołków grafu. W standardowych modelach wykresów losowych zazwyczaj występuje co najwyżej jeden gigantyczny składnik.
obwód
Obwód wykresu jest długością najkrótszej cyklu.
wykres
Podstawowy przedmiot badań w teorii grafów, układ wierzchołków połączonych parami krawędziami. Często podzielone na grafy skierowane lub grafy nieskierowane w zależności od tego, czy krawędzie mają orientację, czy nie. Wykresy mieszane zawierają oba rodzaje krawędzi.
chciwy
Wyprodukowane przez zachłanny algorytm . Na przykład zachłanne kolorowanie wykresu to kolorowanie powstałe 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. Wykres Grötzscha , najmniejszy bez trójkątów wykres wymagający czterech kolorów w dowolnym odpowiednim kolorze.
3.   Twierdzenie Grötzscha, że grafy planarne bez trójkątów mogą być zawsze pokolorowane co najwyżej trzema kolorami.
Numer Grundy
1. Liczba Grundy'ego wykresu to maksymalna liczba kolorów wytworzonych przez zachłanne kolorowanie ze źle dobraną kolejnością 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 -coloring grafu G (gdzie H jest wykresem) jest homomorfizmem od H do G .
H- wolny
Wykres jest wolny od H, jeśli nie ma podgrafu indukowanego izomorficznego z H , to znaczy, jeśli H jest podgrafem zabronionym. Do H wykresy -Darmowe są rodziną wszystkich wykresach (lub, często, wszystkie skończonych wykresy), które są H -Darmowy. Na przykład wykresy bez trójkątów to wykresy, które nie mają wykresu trójkątnego jako podgrafu. Właściwość bycia wolnym od H jest zawsze dziedziczna. Wykres jest wolny od H -moll, jeśli nie ma najmniejszej izomorfii z H .
Hadwigera
1.   Hugo Hadwigera
2. Liczba Hadwigera grafu jest rzędem największego pełnego mola mniejszego grafu. Jest również nazywany liczbą kliki skurczowej lub stopniem homomorfizmu.
3. Przypuszczenie Hadwigera to przypuszczenie, że liczba Hadwigera nigdy nie jest mniejsza niż liczba chromatyczna.
hamiltonian
Hamiltona ścieżka lub cykl Hamiltona jest prosty obejmujące ścieżkę lub prosty cykl rozpinające: obejmuje wszystkie wierzchołki w grafie dokładnie raz. Wykres jest hamiltonowski, jeśli zawiera cykl hamiltonowski, i jest możliwy do prześledzenia, jeśli zawiera ścieżkę hamiltonowską.
przystań
A k - haven to funkcja, która odwzorowuje każdy zbiór X o liczbie mniejszej niż k wierzchołków na jeden z jej płatów, często spełniając dodatkowe warunki spójności. Kolejność przystani to liczba k . Przystani można wykorzystać do scharakteryzowania szerokości drzewa grafów skończonych oraz końców i liczb Hadwigera grafów nieskończonych.
wzrost
1. Wysokość węzła w ukorzenionym drzewie to liczba krawędzi w maksymalnej ścieżce odchodzącej od korzenia (czyli jego węzły mają ściśle rosnącą głębokość), która zaczyna się w tym węźle i kończy się na liściu.
2. Wysokość ukorzenionego drzewa to wysokość jego korzenia. Oznacza to, że wysokość drzewa to liczba krawędzi w najdłuższej możliwej ścieżce, odchodzącej od korzenia, która zaczyna się u nasady i kończy na liściu.
3. Wysokość o skierowanej acykliczny wykresu jest maksymalna długość kierunek ruchu ścieżki na tym wykresie.
dziedziczny
Dziedziczne właściwość wykresów jest właściwością, która jest zamknięta na podstawie wywołanych subgraphs: jeśli G ma właściwość dziedziczne, a więc muszą co indukowana podgrafu o G . Porównaj monotoniczne (zamknięte pod wszystkimi podgrafami) lub moll-zamknięte (zamknięte pod nieletnimi).
sześciokąt
Prosty cykl składający się z dokładnie sześciu krawędzi i sześciu wierzchołków.
otwór
Dziura to indukowany cykl o długości cztery lub więcej. Dziwna dziura to dziura o nieparzystej długości. Anty-dziura jest indukowanym podgrafem rzędu czwartego, którego dopełnieniem jest cykl; równoważnie jest to dziura w grafie dopełnienia. Terminologii tej używa się głównie w kontekście grafów doskonałych, które charakteryzują się twierdzeniem o silnym grafie doskonałym jako grafy bez nieparzystych dziur lub nieparzystych antydziur. Wykresy bezotworowe są takie same jak wykresy akordowe .
równoważność homomorficzna
Dwa grafy są homomorficznie równoważne, jeśli istnieją dwa homomorfizmy, jeden z każdego grafu na drugi.
homomorfizm
1. Homomorfizm grafu to mapowanie ze zbioru wierzchołków jednego grafu do zbioru wierzchołków innego grafu, które mapuje sąsiednie wierzchołki na sąsiednie wierzchołki. Ten typ mapowania między grafami jest najczęściej używany w podejściach 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 minor.
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
Wykres hipersześcian wykres utworzony z wierzchołków i krawędzi geometrycznego hipersześcianu .
hipergraf
Hipergraf uogólnieniem wykres, w którym każda krawędź (nazywany hyperedge w związku) może mieć więcej niż dwa punkty końcowe.
hipo-
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 hamiltonowskiego, ale dla którego każde usunięcie jednego wierzchołka daje podgraf hamiltonowski. Porównaj krytyczne , używane dla wykresów, które mają właściwość, ale dla których nie ma żadnego usunięcia jednego wierzchołka.

i

w stopniu
Liczba nadchodzących krawędzi w grafie skierowanym; zobacz stopień .
zakres
Zapadalność na wykresie znajduje się para wierzchołków krawędzią tak, że wierzchołek jest punktem końcowym krawędzi.
macierz występowania
Matrycy częstość wykresu jest macierzą, której rzędy są indeksowane wierzchołków grafu i których kolumny są indeksowane przez krawędzie, z jednego w komórce dla rzędu I i kolumny j , gdy wierzchołek i krawędziowanie J pada i zero w przeciwnym razie.
incydent
Relacja między krawędzią a jednym z jej punktów końcowych.
nieporównywalność
Wykres nieporównywalności jest uzupełnieniem wykresu porównywalności ; zobacz porównywalność .
niezależny
1. Zbiór niezależny to zbiór wierzchołków, który indukuje podgraf bez krawędzi. Można go również nazwać zestawem stabilnym lub kokliką. Liczba niezależności α ( G ) jest wielkością maksymalnego niezależnego zbioru .
2. W matrycy graficznej grafu podzbiór krawędzi jest niezależny, jeśli odpowiadający mu podgraf jest drzewem lub lasem. W matroidzie dwukołowym podzbiór krawędzi jest niezależny, jeśli odpowiadający mu podgraf jest pseudolasem .
obojętność
Wykres obojętność jest inna nazwa odpowiedniego wykresu odstępach czasu lub jednostkę odstępu wykres; zobacz właściwe .
wywołany
Wywołane subgraph lub pełne subgraph wykresu jest subgraph utworzone z podzbioru wierzchołków i od wszystkich brzegów, które mają obydwa punkty końcowe w podgrupie. Przypadki specjalne obejmują indukowane ścieżki i indukowane cykle , indukowane podgrafy będące ścieżkami lub cyklami.
indukcyjny
Synonim degenerate .
nieskończony
Wykres nieskończony to taki, który nie jest skończony; zobacz skończone .
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ą wspólnego wierzchołka, z wyjątkiem pierwszego i ostatniego.
skrzyżowanie
1. Przecięcie 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 odpowiadające dwa zbiory lub obiekty mają niepuste przecięcie. Kilka klas grafów można zdefiniować jako grafy przecięcia niektórych typów obiektów, na przykład grafy akordowe ( wykresy przecięcia poddrzewa), grafy kołowe (wykresy przecięcia cięciw koła), grafy interwałowe (wykresy przecięcia przedziałów). linii), wykresy liniowe ( wykresy przecięcia krawędzi grafu) oraz wykresy klików (wykresy przecięcia maksymalnych klik grafu). Każdy graf jest grafem przecięcia dla pewnej rodziny zbiorów, a ta rodzina nazywana jest reprezentacją przecięcia grafu. Liczba przecięcia grafu G jest minimalna liczba elementów w dowolnej reprezentacji przecięcia G .
interwał
1. Odstęp wykres jest wykresem przecięcia z przedziałów linii .
2. Przedział [ u , v ] w 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łasności .
odwrócona strzałka
Strzałka z przeciwnym kierunku w stosunku do innego strzałką. Strzałka ( y , x ) to odwrócona strzałka strzałki ( x , y ) .
odosobniony
Izolowany wierzchołek grafu to wierzchołek o stopniu równym zero, czyli wierzchołek bez krawędzi padających.
izomorficzny
Dwa grafy są izomorficzne, jeśli istnieje między nimi izomorfizm; zobacz izomorfizm .
izomorfizm
Wykres Izomorfizm jest jeden-do-jednego częstość zachowując zgodność z wierzchołków i krawędzi jednego wykresu na wierzchołkach i krawędziach innego wykresu. Mówi się, że dwa wykresy powiązane w ten sposób są izomorficzne.
izoperimetryczny
Zobacz rozszerzenie .
przesmyk
Synonim bridge , w znaczeniu krawędzi, której usunięcie rozłącza wykres.

K

K
Notacja dla kompletnych wykresów, pełnych wykresów dwudzielnych i pełnych wykresów wieloczęściowych, patrz complete .
κ
κ ( G ) (używając greckiej litery kappa) jest rzędem maksymalnej kliki w G ; zobacz klika .
jądro
Jądro grafu skierowanego to zbiór wierzchołków, który jest jednocześnie stabilny i absorbujący .
węzeł
Nieunikniona część grafu skierowanego . Zobacz węzeł (matematyka) i teoria węzłów .

L

L
L ( G ) jest wykresem liniowym z G ; patrz linia .
etykieta
1. Informacje związane z wierzchołkiem lub krawędzią grafu. Wykres z etykietą to wykres, którego wierzchołki lub krawędzie mają etykiety. Terminy vertex-labeled lub edge-labeled mogą być używane do określenia, które obiekty wykresu mają etykiety. Etykietowanie wykresów odnosi się do kilku różnych problemów związanych z przypisywaniem etykiet do wykresów z pewnymi ograniczeniami. Zobacz także kolorowanie wykresu , w którym etykiety są interpretowane jako kolory.
2. W kontekście enumeracji grafów wierzchołki grafu są etykietowane, jeśli wszystkie można od siebie odróżnić. Na przykład można to zrobić, ustalając zgodność jeden do jednego między wierzchołkami a liczbami całkowitymi od 1 do rzędu na wykresie. Gdy wierzchołki są oznaczone etykietami, grafy, które są względem siebie izomorficzne (ale z różnymi porządkami wierzchołków) są liczone jako oddzielne obiekty. W przeciwieństwie do tego, gdy wierzchołki są nieoznakowane, wykresy, które są względem siebie izomorficzne, nie są liczone oddzielnie.
liść
1. Wierzchołek liścia lub wiszący wierzchołek (zwłaszcza w drzewie) to wierzchołek o stopniu  1 . Krawędź liścia lub krawędź zwisająca to krawędź łącząca wierzchołek liścia z jego pojedynczym sąsiadem.
2. Siła liści drzewa to graf, którego wierzchołkami są liście drzewa i którego krawędzie łączą liście, których odległość w drzewie wynosi co najwyżej zadany próg.
długość
Na wykresie nieważonym długość cyklu, ścieżki lub spaceru to liczba użytych krawędzi. Na wykresie ważonym może zamiast tego być sumą wag krawędzi, których używa. Długość służy do zdefiniowania najkrótszej ścieżki , obwodu (najkrótszej długości cyklu) i najdłuższej ścieżki między dwoma wierzchołkami na wykresie.
poziom
1. Jest to głębokość węzła plus 1, chociaż niektórzy definiują ją jako synonim głębokości . Poziom węzła w drzewie zakorzenionym 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 linii L ( G ) grafu G wykres z wierzchołka dla każdej krawędzi G oraz krawędź każdej pary krawędzi, które dzielą się koniec w G .
połączenie
Synonim degeneracji .
lista
1. Lista sąsiedztwa to komputerowa reprezentacja grafów do wykorzystania w algorytmach grafowych.
2.   Kolorowanie listy to odmiana kolorowania wykresu, w której każdy wierzchołek ma listę dostępnych kolorów.
lokalny
Lokalna właściwość grafu to właściwość, która jest określana tylko przez sąsiedztwo wierzchołków grafu. Na przykład graf jest lokalnie skończony, jeśli wszystkie jego sąsiedztwa są skończone.
pętla
Pętli lub siebie pętli krawędź oba punkty końcowe, których wierzchołki są takie same. Tworzy cykl o długości 1 . Nie są one dozwolone w prostych wykresach.

m

powiększenie
Synonim rozszerzenia wierzchołków .
dopasowanie
Dopasowanie jest zbiorem krawędzi, w których nie ma dwóch udostępnia żadnych wierzchołek. Wierzchołek jest dopasowany lub nasycony, jeśli jest jednym z punktów końcowych krawędzi w dopasowaniu. Dopasowanie doskonały lub całkowite dopasowanie jest dopasowanie że pasuje do każdego wierzchołka; może być również nazywany czynnikiem 1 i może istnieć tylko wtedy, gdy kolejność jest parzysta. Prawie idealne dopasowanie na wykresie w nieparzystym porządku to takie, które nasyca wszystkie wierzchołki poza jednym. Dopasowanie maksymalna jest dopasowanie, że wykorzystanie wielu krawędziach, jak jest to możliwe; liczba dopasowania α ′( G ) grafu G jest liczbą krawędzi w maksymalnym dopasowaniu. Dopasowanie ilość jest dopasowanie do którego żadne dodatkowe krawędzie mogą być dodawane.
maksymalny
1. Podgraf danego grafu G jest maksymalny dla danej właściwości, jeśli ma tę właściwość, ale żaden inny jego supergraf, który jest również podgrafem G, również ma taką samą właściwość. Oznacza to, że jest to maksymalny element podgrafów z własnością. Na przykład maksymalna klika jest pełnym podgrafem, którego nie można rozszerzyć do większego pełnego podgrafu. Słowo „maksymalne” należy odróżnić od „maksymalnego”: podgraf maksimum jest zawsze maksymalny, ale niekoniecznie odwrotnie.
2. Prosty graf z daną właściwością jest maksymalny dla tej właściwości, jeśli nie można do niego dodać kolejnych krawędzi (zachowując niezmieniony zestaw wierzchołków), przy jednoczesnym zachowaniu prostoty grafu i właściwości. Tak więc, na przykład, maksymalny graf planarny jest grafem planarnym takim, że dodanie do niego kolejnych krawędzi stworzyłoby graf nieplanarny.
maksymalny
Podgraf danego grafu G jest maksymalny dla danej właściwości, jeśli jest największym podgrafem (według kolejności lub wielkości) wśród wszystkich podgrafów o tej 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, szczególnie w grafach medianowych i grafach modularnych .
2. Wykres mediany to wykres, w którym każde trzy wierzchołki mają unikalną medianę.
Meyniel
1. Henri Meyniel, francuski teoretyk grafów.
2. Wykres Meyniela to wykres, w którym każdy nieparzysty cykl o długości pięć lub więcej ma co najmniej dwa akordy.
minimalny
Podgraf danego grafu jest minimalny dla danej właściwości, jeśli ma tę właściwość, ale żaden właściwy podgraf nie ma również tej samej właściwości. Oznacza to, że jest to minimalny element podgrafów z własnością.
minimalne cięcie
Cięcia , którego wyłącznik zestaw posiada minimalny ciężar całkowity, ewentualnie ograniczone do kawałków, które oddzielają się wyznaczony parę wierzchołków; charakteryzują się twierdzeniem o maksymalnym przepływie i przecięciu .
mniejszy
Graf H jest podrzędną innego grafu G, jeśli H można uzyskać, usuwając krawędzie lub wierzchołki z G i skracając krawędzie w G . Jest płytką molową, jeśli można ją uformować jako molową w taki sposób, że podgrafy G, które zostały skrócone, aby utworzyć wierzchołki H, mają małą średnicę. H jest topologiczna drobne z G , jeżeli G jest subgraph który jest podpodział z H . Wykres jest wolny od H -moll, jeśli nie zawiera H -moll. Rodzina grafów jest nieletnia-zamknięta, jeśli jest zamknięta pod nieletnimi; Robertson-Seymour twierdzenie charakteryzuje drobnych zamknięte rodzin o skończony zestaw zabronionych opieki.
mieszany
Miesza wykres przedstawia wykres, który może obejmować zarówno ukierunkowane i nieukierunkowane krawędzie.
modułowy
1.   Graf modułowy , graf , w którym każda trójka wierzchołków ma co najmniej jeden wierzchołek środkowy należący do najkrótszych ścieżek między wszystkimi parami trójki.
2.   Dekompozycja modułowa , dekompozycja grafu na podgrafy, w której wszystkie wierzchołki łączą się z resztą grafu w ten sam sposób.
3.   Modułowość skupienia grafu, różnica liczby krawędzi między skupieniami od wartości oczekiwanej.
monotonia
Monotonna własność grafów to własność, która jest zamknięta pod podgrafami: jeśli G ma własność dziedziczną, to musi ją mieć każdy podgraf G . Porównaj dziedziczne (zamknięte pod indukowanymi podpunktami) lub małoletnie-zamknięte (zamknięte pod nieletnimi).
Wykres Moore'a
Moore wykres jest graf regularny dla których Moore związana jest dokładnie spełnione. Wiązanie Moore'a to nierówność odnosząca się do stopnia, średnicy i porządku grafu, udowodniona przez Edwarda F. Moore'a . Każdy wykres Moore'a to klatka.
multigraf
Multigraf jest wykresem, który umożliwia wiele przylegania (a często kleiste pętle); wykres, który nie musi być prosty.
wielokrotne sąsiedztwo
Wielokrotne sąsiedztwo lub wielokrotna krawędź to zbiór 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). Wykres z wieloma krawędziami jest często nazywany multigrafem.
wielość
Wielość krawędzi to liczba krawędzi w wielokrotnym sąsiedztwie. Wielokrotność grafu to maksymalna krotność którejkolwiek 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 sąsiadujący z danym wierzchołkiem.
sąsiedztwo
sąsiedztwo
Otwarty sąsiedztwo (lub sąsiedztwo) o wierzchołek V jest subgraph indukowanej przez wszystkie wierzchołki, które sąsiadują z v . Sąsiedztwo zamknięte jest definiowane w ten sam sposób, ale obejmuje również samo v . Otwarte sąsiedztwo v w G może być oznaczone jako N G ( v ) lub N ( v ) , a zamknięte sąsiedztwo może być oznaczone jako N G [ v ] lub N [ v ] . Gdy nie określono otwartości lub zamknięcia sąsiedztwa, zakłada się, że jest ono otwarte.
sieć
Wykres, w którym atrybuty (np. nazwy) są powiązane z węzłami i/lub krawędziami.
węzeł
Synonim wierzchołka .
bez krawędzi
Brak krawędzi lub anty-krawędź to para wierzchołków, które nie sąsiadują ze sobą; krawędzie grafu dopełnienia.
wykres zerowy
Zobacz pusty wykres .

O

dziwne
1. Nieparzysty cykl to cykl, którego długość jest nieparzysta. Nieparzyste obwód nie-dwuczęściowego wykresu jest długością najkrótszej nieparzystej cyklu. Dziwny dołek 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 uzgadniania każdy skończony graf nieskierowany ma parzystą liczbę nieparzystych wierzchołków.
3. Nieparzyste ucho to prosta ścieżka lub prosty cykl o nieparzystej liczbie krawędzi, używany w dekompozycji nieparzystego ucha grafów o czynnikach krytycznych; zobacz ucho .
4. Nieparzysty akord to krawędź łącząca dwa wierzchołki znajdujące się w nieparzystej odległości od siebie w cyklu parzystym. Akordy nieparzyste służą do definiowania wykresów silnie akordowych .
5. Graf nieparzysty to szczególny przypadek grafu Knesera , który ma jeden wierzchołek dla każdego ( n − 1) podzbioru -elementowego zestawu (2 n − 1) -elementowego oraz krawędź łączącą dwa podzbiory, gdy odpowiadające im zbiory są nieskładny.
otwarty
1. Zobacz sąsiedztwo .
2. Zobacz 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 ; zobacz pierwsze i drugie zamówienie .
3. Porządek lub uporządkowanie grafu to ułożenie jego wierzchołków w ciąg, zwłaszcza w kontekście uporządkowania topologicznego (porządek skierowanego grafu acyklicznego, w którym każda krawędź przechodzi od wcześniejszego wierzchołka do późniejszego wierzchołka w kolejności ) i porzą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 poznać kolejność schronienia lub jeżyny, zobacz przystań i jeżyna .
orientacja
zorientowany
1. Orientacja grafu nieskierowanego to przypisanie kierunków jego krawędziom, czyniąc go grafem skierowanym. Wykres zorientowany to taki, któremu przypisano orientację. Na przykład drzewo poligonowe jest drzewem zorientowanym; różni się od drzewa skierowanego (arborescencyjnego) 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, które są silnie powiązane; orientacje acykliczne , orientacje acykliczne; Orientacje Eulera , orientacje , które są Eulera; i orientacje przechodnie , orientacje , które są przechodnie zamknięte.
2. Graf zorientowany, używany przez niektórych autorów jako synonim grafu skierowanego .
poza stopniem
Zobacz stopień .
zewnętrzny
Zobacz twarz .
zewnętrzny planarny
Outerplanar wykres przedstawia wykres, który może być osadzony w płaszczyźnie (bez przejść), tak, że wszystkie wierzchołki znajdują się na zewnętrznej stronie wykresu.

P

ścieżka
Ścieżki może być w odległości lub bez powtarzanych odległości wierzchołków, a tym samym krawędzi (zwany także drogą prosty), w zależności od źródła. Ważnymi przypadkami specjalnymi są ścieżki indukowane i ścieżki najkrótsze .
dekompozycja ścieżki
Ścieżka rozkładu grafu G jest rozkład drzewa którego bazowego drzewa jest droga. Jego szerokość określa się w taki sam sposób jak dla rozkładu drzew, jako o jeden mniejszy niż rozmiar największego worka. Minimalna szerokość dowolnej dekompozycji ścieżki G to szerokość ścieżki G .
szerokość ścieżki
Pathwidth grafu G jest minimalna szerokość rozkładu po torze G . Można go również zdefiniować w kategoriach liczby kliki uzupełnienia interwału G . Jest zawsze pomiędzy przepustowością a szerokością drzewa G . Jest również znany jako grubość interwału, numer separacji wierzchołków lub numer wyszukiwania węzłów.
wisiorek
Zobacz liść .
doskonały
1. Doskonały graf to taki graf, w którym w każdym indukowanym podgrafie liczba chromatyczna jest równa liczbie kliki. Twierdzenie o idealnym grafie i twierdzenie o silnym idealnym grafie to dwa twierdzenia dotyczące doskonałych grafów, z których pierwsze dowodzi, że ich uzupełnienia również są doskonałe, a drugie dowodzi, że są to dokładnie grafy bez nieparzystych dziur lub antydziur.
2. Graf doskonale uporządkowany to graf, którego wierzchołki mogą być uporządkowane w taki sposób, że algorytm zachłannego kolorowania z tym uporządkowaniem optymalnie koloruje każdy indukowany podgraf. Idealnie uporządkowane wykresy są podklasą doskonałych wykresów.
3. Idealne dopasowanie to dopasowanie, które nasyca każdy wierzchołek; zobacz dopasowywanie .
4. Idealna 1-faktoryzacja to podział krawędzi grafu na idealne dopasowania tak, aby każde dwa dopasowania tworzyły cykl hamiltonowski.
peryferyjny
1. Cykl obwodowy lub cykl nierozdzielający to cykl z co najwyżej jednym mostkiem.
2. Wierzchołek obwodowy to wierzchołek, którego mimośród jest maksymalny. Na drzewie to musi być liść.
Petersen
1.   Julius Petersen (1839-1910), duński teoretyk grafów.
2. Wykres Petersena , 10-wierzchołkowy wykres 15-krawędziowy często używany jako kontrprzykład.
3.   Twierdzenie Petersena, że każdy bezmostkowy graf sześcienny ma idealne dopasowanie.
planarny
Płaska wykres jest wykresem, który ma osadzenie na euklidesowej płaszczyźnie. Wykres płaski to wykres planarny, dla którego określone osadzanie zostało już ustalone. K wykres -planar jest, że można wyciągnąć na płaszczyźnie co najwyżej k przejść na krawędź.
polidrzewo
Polytree jest zorientowany drzewo; równoważnie skierowany graf acykliczny, którego podstawowym grafem nieskierowanym jest drzewo.
moc
1. Potęga grafu G k grafu G jest innym grafem na tym samym zbiorze wierzchołków; dwa wierzchołki sąsiadują ze sobą w G k, gdy znajdują się w odległości co najwyżej k w G . Moc liść jest ściśle powiązany pojęcie, pochodzące z mocy drzewa biorąc podgrafu wywołaną przez liści drzewa za.
2.   Analiza grafów mocy to metoda analizy złożonych sieci poprzez identyfikowanie klik, bików i gwiazd w sieci.
3.   prawo energetyczne w stopnia rozkładu z sieci skalę wolne są zjawiskiem, w którym liczba wierzchołków danego stopnia jest proporcjonalny do stopnia mocy.
poprzednik
Wierzchołek pochodzących przed danego wierzchołka w kierunek ruchu ścieżki .
właściwy
1. Podgraf właściwy to podgraf, który usuwa przynajmniej jeden wierzchołek lub krawędź względem całego grafu; dla grafów skończonych podgrafy właściwe nigdy nie są izomorficzne w stosunku do całego grafu, ale dla grafów nieskończonych mogą być.
2. Właściwe kolorowanie to przypisanie kolorów do wierzchołków grafu (kolorowanie), które przypisuje różne kolory do punktów końcowych każdej krawędzi; zobacz kolor .
3. Właściwy wykres przedziału 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ł lub łuk nie zawiera innego przedziału lub łuku. Właściwe wykresy interwałowe są również nazywane wykresami interwałów jednostkowych (ponieważ zawsze mogą być reprezentowane przez interwały jednostkowe) lub wykresami obojętności.
własność
Nieruchomość wykres jest coś, co może być prawdą w niektórych wykresach i fałsz od innych, a to zależy tylko od struktury grafu, a nie przypadkowych informacji, takich jak etykiety. Właściwości grafów można równoważnie opisać w kategoriach klas grafów (grafów, które mają daną właściwość). Mówiąc bardziej ogólnie, właściwość grafu może być również funkcją grafów, która jest znowu niezależna od przypadkowych informacji, takich jak rozmiar, kolejność lub sekwencja stopni grafu; ta bardziej ogólna definicja właściwości jest również nazywana niezmiennikiem grafu.
pseudolas
Pseudoforest jest nieukierunkowane wykres, w którym każdy składnik jest połączone najwyżej jeden cykl, lub skierowane wykres, na którym każdy wierzchołek ma co najwyżej jedną krawędź wychodzącego.
pseudograf
Pseudograf to graf lub multigraf, który umożliwia tworzenie własnych pętli.

Q

wykres quasi-liniowy
Wykres quasi-liniowy lub graf lokalnie współdzielony to graf, w którym otwarte sąsiedztwo każdego wierzchołka można podzielić na dwie kliki. Wykresy te są zawsze pozbawione pazurów i zawierają w specjalnym przypadku wykresy liniowe . Wykorzystywane są w teorii struktury grafów bezpazurowych.
kołczan
Kołczan jest skierowany multigraf, stosowany w teorii kategorii . Krawędzie kołczanu nazywane są strzałami.

r

promień
Promień wykresu to minimalny mimośród dowolnego wierzchołka.
Ramanujan
Ramanujana wykres przedstawia wykres widmowy, których rozbudowa jest tak duży jak to możliwe. Oznacza to, że jest to wykres d- regularny, taki, że druga co do wielkości wartość własna jego macierzy sąsiedztwa wynosi co najwyżej .
promień
Promień na nieskończonym wykresie jest nieskończoną prostą ścieżką z dokładnie jednym punktem końcowym. Te końce wykresu są równoważności klas promieni.
osiągalność
Możliwość przejścia z jednego wierzchołka do drugiego w obrębie wykresu .
osiągalny
Ma osiągalność twierdzącą . Wierzchołek Y mówi się osiągalne z wierzchołkiem x jeśli istnieje ścieżka od x do y .
rozpoznawalny
W kontekście przypuszczenia rekonstrukcji właściwość grafu jest rozpoznawalna, jeśli jej prawdziwość można określić z pokładu grafu. Wiadomo, że wiele właściwości wykresów jest rozpoznawalnych. Jeśli hipoteza rekonstrukcji jest prawdziwa, wszystkie właściwości grafu są rozpoznawalne.
rekonstrukcja
Rekonstrukcji przypuszczenie stwierdza, że każdy nieukierunkowane wykres G jest jednoznacznie wyznaczona przez jego pokład , A multiset wykresów tworzone przez usunięcie jednego wierzchołka z G we wszystkich możliwych sposobów. W tym kontekście rekonstrukcja to tworzenie wykresu z jego talii.
prostokąt
Prosty cykl składający się z dokładnie czterech krawędzi i czterech wierzchołków.
regularny
Wykres jest d- regularny, gdy wszystkie jego wierzchołki mają stopień d . Graf regularny to wykres, który jest d -regular jakiegoś d .
regularny turniej
Zwykły turniej to turniej, w którym stopień wejściowy jest równy stopniowi końcowemu dla wszystkich wierzchołków.
odwrócić
Zobacz transponować .
źródło
1. Wyznaczony wierzchołek w grafie, szczególnie w drzewach skierowanych i grafach ukorzenionych .
2. Operacja odwrotna do potęgi grafu : k- ty pierwiastek grafu G jest innym grafem na tym samym zbiorze wierzchołków, tak że dwa wierzchołki sąsiadują w G wtedy i tylko wtedy, gdy mają odległość co najwyżej k w pierwiastku.

S

drugie zamówienie
Logika grafów drugiego rzędu 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 testowania, czy wierzchołek i krawędź są incydentami, a także czy wierzchołek lub krawędź należy do zestawu. Należy odróżnić od logiki pierwszego rzędu, w której zmienne mogą reprezentować tylko wierzchołki.
nasycony
Zobacz dopasowywanie .
numer wyszukiwania
Numer wyszukiwania węzła jest synonimem dla pathwidth .
pętla własna
Synonim pętli .
oddzielający wierzchołek
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 wielu sąsiedztw. 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, powtarzających się krawędzi.
tonąć
Ujście, w grafie skierowanym, jest wierzchołkiem bez krawędzi wychodzących (stopień na zewnątrz równa się 0).
rozmiar
Wielkość grafu G to liczba jego krawędzi, | E ( G )| . Zmienna m jest często używana dla tej wielkości. Zobacz także kolejność , liczba 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 definiuje się 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 sieci
snark
Snark jest prosty, połączony bezmostkowego sześcienny wykres z indeksem chromatycznej równa 4.
źródło
Źródło w grafie skierowanym to wierzchołek bez krawędzi (w stopniach równych 0).
przestrzeń
W algebraicznej teorii grafów kilka przestrzeni wektorowych nad polem binarnym może być powiązanych z grafem. Każdy ma zestawy krawędzi lub wierzchołków dla swoich wektorów i symetryczną różnicę zbiorów jako operację sumy wektorowej. Przestrzeń krawędzi jest przestrzenią wszystkich zbiorów krawędzi, a przestrzeń wierzchołków jest przestrzenią wszystkich zbiorów wierzchołków. Przestrzeń cięta to podprzestrzeń przestrzeni brzegowej, której elementami są wycięte zbiory grafu. Przestrzeń cyklu ma jako swoje elementy rozpinające się podgrafy Eulera.
klucz do nakrętek
Spanner to (zwykle rzadki) wykres, którego najkrótsze odległości ścieżki są zbliżone do odległości w gęstym wykresie lub innej przestrzeni metrycznej. Wariacje obejmują klucze geometryczne , wykresy, których wierzchołki są punktami w przestrzeni geometrycznej; klucze drzew , drzewa opinające grafu, których odległości przybliżają odległości grafu, oraz klucze grafu, nieliczne podgrafy gęstego grafu, których odległości przybliżają odległości oryginalnego grafu. Chciwy klucz to klucz grafowy skonstruowany przez zachłanny algorytm, ogólnie taki, który uwzględnia wszystkie krawędzie od najkrótszych do najdłuższych i zachowuje te, które są potrzebne do zachowania przybliżenia odległości.
łączenie
Podwykres obejmuje wszystkie wierzchołki danego wykresu. Ważne przypadki obejmują drzewa opinające , podgrafy opinające będące drzewami oraz idealne dopasowania , podgrafy opinające będące dopasowaniami. Podwykres rozpinający można również nazwać współczynnikiem , zwłaszcza (ale nie tylko), gdy jest regularny.
rzadki
Rzadki wykresu jest taki, który ma kilka krawędzi w stosunku do jego liczby wierzchołków. W niektórych definicjach ta sama własność powinna być również prawdziwa dla wszystkich podgrafów danego grafu.
widmowy
widmo
Widmo grafu to zbiór wartości własnych macierzy sąsiedztwa. Teoria grafów spektralnych jest gałęzią teorii grafów, która wykorzystuje widma do analizy grafów. Zobacz także ekspansja widmowa .
podział
1. Graf dzielony to graf, którego wierzchołki można podzielić na klikę i niezależny zbiór. 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, tak że krawędzie obejmujące to cięcie tworzą kompletny podgraf dwudzielny. Podziały grafu mogą być reprezentowane przez strukturę drzewa zwaną jego rozkładem podziału . Rozłam nazywany jest silnym rozłamem, gdy nie jest przecinany przez żaden inny rozłam. Podział nazywa się nietrywialnym, gdy obie jego strony mają więcej niż jeden wierzchołek. Wykres nazywa się liczbą pierwszą, 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 z dwustronnym wykresu jest subgraph jego kwadratu indukowanej przez jednej stronie bipartition.
2. Wykres kwadratowy to płaski wykres, który można narysować tak, aby wszystkie ograniczone ściany były 4-cyklowe, a wszystkie wierzchołki stopnia ≤ 3 należały do ​​zewnętrznej ściany.
3. Graf z siatką kwadratową to graf sieciowy zdefiniowany z 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 jest drzewo z jednym wewnętrznym wierzchołka; równoważnie jest to zupełny dwudzielny graf K 1, n dla pewnego n ≥ 2 . Specjalny przypadek gwiazdy z trzema liśćmi nazywa się pazurem.
siła
Siła wykresu jest stosunek minimalnej liczby krawędzi usuwa się z wykresu na składniki utworzonego w stosunku do wszystkich możliwych pochłaniania; 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ładowych grafów skierowanych, zobacz spójne i składowe . Silne ukierunkowanie jest orientacji, która jest silnie związane; patrz orientacja .
2. Dla twierdzenia o silnym grafie doskonałym , zobacz perfect .
3. Graf silnie regularny to graf regularny, w którym co dwa sąsiednie wierzchołki mają taką samą liczbę wspólnych sąsiadów, a każde dwa niesąsiadują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ść lub więcej ma akord nieparzysty.
5. Graf silnie doskonały to taki, w którym każdy podgraf indukowany ma niezależny zbiór spełniający wszystkie maksymalne kliki. Te wykresy Meyniel nazywane są również „bardzo silnie graf doskonały”, ponieważ w nich, każdy wierzchołek należy do takiego niezależnego zestawu.
podlas
Podgraf lasu .
podpunkt
Podwykres grafu G to kolejny graf utworzony z podzbioru wierzchołków i krawędzi 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 obejmujący to taki, który zawiera wszystkie wierzchołki grafu; podwykres indukowany to taki, który zawiera wszystkie krawędzie, których punkty końcowe należą do podzbioru wierzchołków.
poddrzewo
Poddrzewo to połączony podgraf drzewa. Czasami w przypadku drzew ukorzenionych poddrzewa definiuje się jako specjalny rodzaj połączonego podgrafu, utworzonego przez wszystkie wierzchołki i krawędzie osiągalne z wybranego wierzchołka.
następca
Wierzchołek pochodzące od danego wierzchołka w kierunek ruchu ścieżki .
superkoncentrator
Superkoncentrator to graf z dwoma wyznaczonymi i równymi podzbiorami wierzchołków I i O , tak że dla każdych dwóch jednakowych 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ł ukierunkowanym grafem acyklicznym, z I jako jego źródłami i O jako jego spadkami.
supergraf
Wykres utworzony przez dodanie wierzchołków, krawędzi lub obu do danego wykresu. Jeśli H jest podgrafem G , to G jest supergrafem H .

T

theta
1. Wykres theta jest sumą trzech wewnętrznie rozłącznych (prostych) ścieżek, które mają te same dwa różne wierzchołki końcowe.
2. Wykres theta zbioru punktów na płaszczyźnie euklidesowej jest konstruowany przez skonstruowanie układu stożków otaczających każdy punkt i dodanie jednej krawędzi na stożek do punktu, którego rzut na centralny promień stożka jest najmniejszy.
3. Liczba Lovásza lub funkcja Lovász theta grafu jest niezmiennikiem grafu związanym z liczbą kliki i liczbą chromatyczną, które można obliczyć w czasie wielomianowym za pomocą programowania półokreślonego.
topologiczny
1. Graf topologiczny to reprezentacja wierzchołków i krawędzi grafu za pomocą punktów i krzywych na płaszczyźnie (niekoniecznie z pominięciem przecięć).
2.   Topologiczna teoria grafów zajmuje się badaniem zanurzeń grafów.
3.   Sortowanie topologiczne to problem algorytmiczny polegający na uporządkowaniu ukierunkowanego grafu acyklicznego w porządek topologiczny, taki ciąg wierzchołków, że każda krawędź przechodzi od wcześniejszego wierzchołka do późniejszego wierzchołka w sekwencji.
całkowicie odłączony
Synonim bez krawędzi .
wycieczka
Szlak zamknięty, czyli spacer, który zaczyna się i kończy w tym samym wierzchołku i nie ma powtarzających się krawędzi. Trasy Eulera to trasy wykorzystujące wszystkie krawędzie grafu; patrz Eulerowski .
Turniej
Turnieju jest orientacja całkowitego wykres; oznacza to, że jest to graf skierowany, tak że każde dwa wierzchołki są połączone dokładnie jedną skierowaną krawędzią (prowadzącą tylko w jednym z dwóch kierunków między dwoma wierzchołkami).
identyfikowalny
Identyfikowalne wykres jest wykresem, który zawiera ścieżki Hamiltona.
trasa
Spacer bez powtarzających się krawędzi.
przechodni
Ma do czynienia z własnością przechodnią . Przechodni zamknięcia danego skierowanej wykres przedstawia wykres tego samego zestawu wierzchołka, która ma krawędź, z jednym wierzchołkiem do drugiego, gdy oryginalny wykres ma ścieżkę łączącą te same dwa wierzchołki. Przechodni zmniejszenie wykresu jest minimalne wykresu o tej samej przechodni zamykania; ukierunkowane wykresy acykliczne charakteryzują się unikalną redukcją przechodnią. Orientacji przechodni jest orientacja wykresem, który jest jej własny zamknięcie przechodni; istnieje tylko dla wykresów porównywalności .
transponować
Wykres transpozycji danego skierowanej wykres przedstawia wykres na tych samych wierzchołkach, przy czym każda krawędź odwróceniu kierunku. Może być również nazywany odwrotnością lub odwrotnością wykresu.
drzewo
1. Drzewo to graf nieskierowany, który jest zarówno połączony, jak i acykliczny, lub graf skierowany, w którym istnieje unikalne przejście od jednego wierzchołka (korzeń drzewa) do wszystkich pozostałych wierzchołków.
2. Drzewo k to graf utworzony przez sklejenie ( k + 1) -klik na wspólnych k -klikach. Drzewo w potocznym znaczeniu to zgodnie z tą definicją jedno drzewo.
rozkład drzewa
Drzewa rozkładu grafu G jest drzewem, których węzły nie są oznakowane zestawów wierzchołków G ; te zestawy nazywane są torbami. Dla każdego wierzchołka v torebki zawierające v muszą indukować poddrzewo drzewa, a dla każdej krawędzi uv musi istnieć torebka zawierająca zarówno u, jak i v . Szerokość rozkładu drzewa jest o jeden mniejsza niż maksymalna liczba wierzchołków w każdym z jego worków; szerokość drzewa z G jest minimalną szerokością dowolnego rozkładu drzewa z G .
szerokość drzewa
Treewidth grafu G jest minimalna szerokość rozkładu drzewa G . Może on również być zdefiniowane w zakresie liczby klika na cięciwy wykonania z G , rzędu od Haven z G , lub rzędu jeżyny z G .
trójkąt
Cykl o długości trzy na wykresie. Trójkąta wolne wykres jest nieukierunkowane wykres, który nie ma żadnych subgraphs trójkąta.
Turán
1.   Pál Turán
2. Wykres Turána jest zrównoważonym, kompletnym grafem wieloczęściowym.
3.   Twierdzenie Turána mówi, że grafy Turána mają maksymalną liczbę krawędzi spośród wszystkich grafów bezklikowych danego rzędu.
4.   Problem cegielni Turána dotyczy minimalnej liczby przecięć na rysunku kompletnego grafu dwudzielnego.

U

bezkierunkowy
Nieukierunkowane wykres przedstawia wykres, w którym obydwa punkty końcowe każdej krawędzi nie różnią się od siebie. Zobacz także skierowane i mieszane . W grafie mieszanym nieskierowana krawędź to znowu taka, w której punkty końcowe nie są od siebie rozróżniane.
mundur
Hipergraf jest k -jednorodny, gdy wszystkie jego krawędzie mają k punktów końcowych, i jednorodny, gdy jest k -jednorodny dla pewnego k . Na przykład, zwykłe wykresy są takie same jak 2 -uniform hipergrafów.
uniwersalny
1. Graf uniwersalny to graf, który zawiera jako podgrafy wszystkie grafy z danej rodziny grafów lub wszystkie grafy danej wielkości lub kolejności w obrębie danej rodziny grafów.
2. Wierzchołek uniwersalny (zwany również wierzchołkiem lub wierzchołkiem dominującym) to wierzchołek sąsiadujący z każdym innym wierzchołkiem na wykresie. 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 powszechnie kwantyfikowany w formule, można nazwać wierzchołkiem uniwersalnym dla tej formuły.
wykres nieważony
Wykres , którego wierzchołki oraz krawędzie a nie przypisano masy s ; przeciwieństwo wykresu ważonego .

V

V
Zobacz zestaw wierzchołków .
wartościowość
Synonim stopnia .
wierzchołek
Wierzchołek (mnogiej wierzchołki) jest (łącznie z krawędziami) jedna z dwóch podstawowych zespołów z których są zbudowane wykresy. Wierzchołki grafów są często uważane za obiekty atomowe, bez wewnętrznej struktury.
cięcie wierzchołka
zestaw oddzielający
Zestaw wierzchołków których usunięcie odłącza ten wykres . Cięcie o jednym wierzchołku nazywane jest punktem artykulacyjnym lub wyciętym wierzchołkiem .
zestaw wierzchołków
Zbiór wierzchołków danego grafu G , czasami oznaczany przez V ( G ) .
wierzchołki
Zobacz wierzchołek .
Wizytowanie
1.   Vadim G. Vizing
2.   Twierdzenie Vizinga, że indeks chromatyczny jest co najwyżej o jeden większy niż maksymalny stopień.
3.   Przypuszczenie Viizinga o liczbie dominacji iloczynów kartezjańskich grafów.
Tom
Suma stopni zbioru wierzchołków.

W

W
Litera W jest używana w notacji dla wykresów kołowych i wykresów wiatraków . Notacja nie jest znormalizowana.
Wagner
1.   Klaus Wagner
2. Wykres Wagnera , ośmiowierzchołkowa drabina Möbiusa.
3.   Twierdzenie Wagnera charakteryzujące grafy planarne przez ich zabronione podrzędne.
4. Wagnera twierdzenie scharakteryzowania K 5 -minor wolne wykresów.
spacerować
Spacer jest skończona lub nieskończona sekwencja od krawędzi , która łączy sekwencję wierzchołków . Spacery są czasami nazywane łańcuchami . Spacer jest otwarty, jeśli jego pierwszy i ostatni wierzchołek są wyraźne, a zamknięty, jeśli się powtarzają.
słabo połączony
Skierowane wykres nazywany jest słabo związany przypadku wymiany wszystkich swoich skierowanych krawędziach nieukierunkowane krawędzi tworzy związek (niekierowanego) wykresu.
waga
Wartość liczbowa przypisana jako etykieta do wierzchołka lub krawędzi wykresu. Waga podgrafu to suma wag wierzchołków lub krawędzi w tym podgrafie.
wykres ważony
Wykres , którego wierzchołki albo krawędzie y przypisano masy s ; dokładniej, graf ważony wierzchołkami ma wagi na wierzchołkach, a graf ważony krawędziami ma wagi na krawędziach.
dobrze ubarwiony
Wybarwione wykres przedstawia wykres, którego wszystkie barwniki chciwy wykorzystać taką samą ilość kolorów.
dobrze zakryty
Również pokryte wykres jest wykresem wszystkich którego ilość niezależne zestawy są tej samej wielkości.
koło
Wykres kołowy wykres utworzony przez dodanie uniwersalnego wierzchołek do zwykłego cyklu.
szerokość
1. Synonim degeneracji .
2. W przypadku innych niezmienników grafu, znanych jako szerokość, zobacz szerokość pasma , szerokość gałęzi , szerokość kliku , szerokość ścieżki i szerokość drzewa .
3. Szerokość dekompozycji drzewa lub dekompozycji ścieżki jest o jeden mniejsza niż maksymalny rozmiar jednego z jego worków i może być użyta do zdefiniowania szerokości drzewa i ścieżki.
4. Szerokość skierowanego grafu acyklicznego to maksymalna kardynalność antyłańcucha.
wiatrak
Wykres wiatrak ma związek z kolekcji klik, wszystkie w tym samym porządku, co siebie, przy czym jeden wspólny wierzchołek należące do wszystkich klik i wszystkie pozostałe wierzchołki krawędzi różne.

Zobacz też

Bibliografia