40 Grafy

Graf – podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami. W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków.

Graf acykliczny – graf niezawierający cykli. W przypadku grafów nieskierowanych spójnych grafy acykliczne są równoważne drzewom, a niespójne – lasom.

Diagram Hassego – graf skierowany przedstawiający częściowy porządek w zbiorze, w odpowiedni sposób przedstawiony graficznie.

Graf doskonały – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu.

Drzewo – graf nieskierowany, który jest acykliczny i spójny, czyli taki graf, że z każdego wierzchołka drzewa można dotrzeć do każdego innego wierzchołka (spójność) i tylko jednym sposobem.

Graf dwudzielny – graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Równoważnie: graf, który nie zawiera cykli nieparzystej długości. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym lub kliką dwudzielną i oznaczamy gdzie i oznaczają liczności zbiorów wierzchołków.

Graf eulerowski, graf Eulera – rodzaj grafu rozpatrywany w teorii grafów. Graf eulerowski odznacza się tym, że da się w nim skonstruować cykl Eulera, czyli cykl, który przechodzi przez każdą jego krawędź dokładnie raz. Pierwszy raz problem poszukiwania cyklów w grafach został podniesiony przez szwajcarskiego matematyka, Leonharda Eulera w roku 1736, który chciał rozwiązać zagadnienie mostów królewieckich. Aby odszukać cykl Eulera w grafie można posłużyć się algorytmem Fleury’ego.

Graf hamiltonowski – graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim.

Hipergraf – rozszerzenie pojęcia grafu. Jego krawędzie, nazywane hiperkrawędziami, mogą być incydentne do dowolnej liczby wierzchołków.

Graf Hoffmana–Singletona jest grafem o następujących parametrach:posiada 50 wierzchołków, posiada 175 krawędzi, stopień każdego wierzchołka wynosi 7, średnica grafu wynosi 2, obwód grafu wynosi 5.

Graf k-dzielny – naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią.

Graf k-spójny to graf spójny, w którym usunięcie mniej niż k dowolnych wierzchołków nie spowoduje jego rozspojenia.

Kograf (ang. cograph, P4-free graph) – graf, który można zbudować z pojedynczych wierzchołków za pomocą operacji złączenia oraz sumowania grafów. Złączenie grafów G i F to graf powstały poprzez połączenie wszystkich wierzchołków grafu G z wszystkimi wierzchołkami grafu F, przy zachowaniu wewnętrznej budowy grafów G i F. Natomiast operacja sumy grafów to zwykłe sumowanie zbiorów krawędzi i wierzchołków.

Graf komórkowy - graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości.

Graf krawędziowy grafu G – taki graf F=L(G), którego zbiorem wierzchołków jest zbiór krawędzi grafu G: V(F) = E(G), natomiast zbiorem krawędzi E(F) jest zbiór par elementów zbioru E(G), przy czym:

Graf kubiczny – graf regularny stopnia 3.

Las - graf, którego każdy spójny podgraf jest drzewem. Równoważnie można zdefiniować las po prostu jako acykliczny graf nieskierowany. Wtedy jego spójne składowe są drzewami.

Graf – podstawowy obiekt rozważań teorii grafów, struktura matematyczna służąca do przedstawiania i badania relacji między obiektami. W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków.

Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca.

Graf Petersena to graf o ciekawych własnościach często używany w teorii grafów. Nazwa pochodzi od nazwiska matematyka J. Petersena, któremu przypisuje się pierwszą publikację na temat grafu w 1898 roku.

Graf planarny – graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim.

Graf platoński - graf którego obraz tworzy siatkę wielościanu foremnego.

Graf płaski - przedstawienie grafu planarnego na płaszczyźnie w taki sposób, że żadne dwie krawędzie grafu się nie przecinają.

Graf podstawowy grafu skierowanego G to nieskierowany graf F w którym pomiędzy wierzchołkami a,b krawędź istnieje wtedy i tylko wtedy, gdy w grafie G istnieje krawędź od a do b lub od b do a. Intuicyjnie tworzenie grafu podstawowego można rozumieć jako usuwanie grotów krawędzi grafu skierowanego.

Graf półeulerowski – graf rozważany w teorii grafów. Graf półeulerowski zawiera w sobie ścieżkę, która pozwala przejść przez wszystkie jego krawędzie tylko raz. Ścieżka ta nazywana jest ścieżką Eulera.

Graf prosty - graf bez pętli własnych i krawędzi wielokrotnych. Często określenie graf oznacza graf prosty.

Graf przedziałowy – graf utworzony ze zbioru odcinków na prostej, poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładają.

Graf przepływu sygnałów – szczególny typ diagramu blokowego – i graf skierowany – składający się z węzłów i gałęzi. W teorii sterowania obok schematu blokowego drugie dogodne narzędzie graficznego opisu złożonych układów regulacji.

Graf regularny stopnia to graf, w którym wszystkie wierzchołki są stopnia czyli z każdego wierzchołka grafu regularnego wychodzi krawędzi. Graf regularny stopnia określa się dla wygody mianem grafu -regularnego. Szczególnym przypadkiem grafów regularnych są grafy kubiczne.

Samodopełniający się graf to graf który jest izomorficzny do swojego dopełnienia. Najprostszym samodopełniającym się grafem jest 4-wierzchołkowa ścieżka oraz 5-wierzchołkowy cykl.

Sieć small-world – rodzaj matematycznego grafu, w którym większość węzłów nie jest w bezpośrednim sąsiedztwie z innymi, ale sąsiedzi każdego danego węzła mogą być swoimi wzajemnymi sąsiadami i większość węzłów sieci może zostać osiągnięta z każdego węzła na drodze niewielkiej liczby kroków. Dokładniej mówiąc, sieć small-world jest definiowana jako sieć, w której średni dystans pomiędzy dwoma losowo wybranymi węzłami rośnie proporcjonalnie do logarytmu liczby węzłów w sieci, to jest:

Sieć złożona to graf o nietrywialnych właściwościach topologicznych. Przykłady takich sieci to: WWW, Internet, sieć współpracy pomiędzy aktorami, sieć współpracy pomiędzy naukowcami, sieć kontaktów seksualnych. W badaniach nad sieciami złożonymi uczestniczą naukowcy z wielu dziedzin, m.in.: matematyki, fizyki, biologii, informatyki, socjologii, epidemiologii.

Graf skierowany – rodzaj grafu rozważanego w teorii grafów. Graf skierowany definiuje się jako uporządkowaną parę zbiorów. Pierwszy z nich zawiera wierzchołki grafu, a drugi składa się z krawędzi grafu, czyli uporządkowanych par wierzchołków. Ruch po grafie możliwy jest tylko w kierunkach wskazywanych przez krawędzie. Graf skierowany można sobie wyobrazić jako sieć ulic, z których każda jest jednokierunkowa. Ruch pod prąd jest zakazany. Najczęściej grafy skierowane przedstawia się jako zbiór punktów reprezentujących wierzchołki połączonych strzałkami albo łukami zakończonymi grotem.

Skierowany graf acykliczny – graf skierowany, który nie posiada cyklów skierowanych. Jest to w informatyce bardzo ważna struktura, łącząca zalety drzew i ogólnych grafów skierowanych.

Graf spójny – graf spełniający warunek, że dla każdej pary wierzchołków istnieje ścieżka, która je łączy.

Stos o strukturze grafowej jest skierowanym grafem acyklicznym gdzie każda skierowana ścieżka reprezentuje stos. Struktura ta jest ważną częścią algorytmu Tomity (GLR) gdzie zastępuje zwykły stos automatu ze stosem jak również GLL Johnstone'a. To pozwala algorytmowi wybierać z powrotami z większą wydajnością.

Graf symetryczny – graf skierowany taki, że jeżeli istnieje krawędź to istnieje też krawędź

Graf Szekeresa - żmirłacz składający się z 50 wierzchołków. Był piątym znanym żmirłaczem; odkryty przez George'a Szekeresa w 1973 roku.

Graf Turána – graf powstały przez podział zbioru wierzchołków na możliwie równych części i połączenie krawędziami tych wierzchołków, które w wyniku podziału znajdą się w różnych podzbiorach.

Żmirłacz – spójny graf kubiczny bez mostów i o indeksie chromatycznym równym 4. Najmniejszym żmirłaczem jest graf Petersena. Co więcej wszystkie żmirłacze zawierają graf Petersena jako minor. Żmirłacze należą do drugiej klasy grafów ze względu na wartość indeksu chromatycznego.