Wykres (matematyka dyskretna) - Graph (discrete mathematics)

Wykres z sześcioma wierzchołkami i siedmioma krawędziami.

W matematyce , a dokładniej w teorii grafów , graf jest strukturą będącą zbiorem obiektów, w którym pewne pary obiektów są w pewnym sensie „powiązane”. Obiekty odpowiadają abstrakcjom matematycznym zwanym wierzchołkami (zwanymi również węzłami lub punktami ), a każda z powiązanych par wierzchołków nazywana jest krawędzią (zwaną również łączem lub linią ). Zazwyczaj wykres jest przedstawiany w formie diagramu jako zestaw kropek lub okręgów dla wierzchołków, połączonych liniami lub krzywymi dla krawędzi. Wykresy są jednym z przedmiotów badań matematyki dyskretnej .

Krawędzie mogą być skierowane lub nieskierowane. Na przykład, jeśli wierzchołki reprezentują ludzi na imprezie i istnieje przewaga między dwiema osobami, jeśli podają sobie rękę, to ten wykres jest nieskierowany, ponieważ każda osoba A może uścisnąć dłoń osobie B tylko wtedy, gdy B poda rękę również z A . W przeciwieństwie do tego, jeśli jakakolwiek krawędź od osoby A do osoby B odpowiada A jest winna pieniądze B , to ten wykres jest skierowany, ponieważ należność za pieniądze niekoniecznie jest odwzajemniona. Pierwszy typ grafu nazywany jest grafem nieskierowanym, a drugi graf nazywany jest grafem skierowanym .

Grafy są podstawowym przedmiotem badań teorii grafów . Słowo „wykres” po raz pierwszy użył w tym sensie JJ Sylvester w 1878 r. w bezpośrednim związku matematyki ze strukturą chemiczną (co nazwał obrazem chemiczno-graficznym).

Definicje

Definicje w teorii grafów są różne. Poniżej przedstawiono niektóre z bardziej podstawowych sposobów definiowania wykresów i powiązanych struktur matematycznych .

Wykres

Wykres z trzema wierzchołkami i trzema krawędziami.

Wykres (czasami nazywane nieukierunkowane wykres dla odróżnienia od skierowanej wykresu lub prosty wykres dla odróżnienia od multigraf ) jest para G = ( V , E ) , gdzie V jest zestaw, której elementy są nazywane wierzchołki (pojedynczej: Vertex), a E to zbiór sparowanych wierzchołków, których elementy nazywane są krawędziami (czasami łączami lub liniami ).

Wierzchołki x i y krawędzi { x , y } nazywane są punktami końcowymi krawędzi. Mówi się, że krawędź łączy się z x i y i jest przypadkowa na x i y . Wierzchołek nie może należeć do żadnej krawędzi, w którym to przypadku nie jest połączony z żadnym innym wierzchołkiem.

Multigraf to uogólnienie, które umożliwia wielokrotne krawędzie mają tę samą parę końcowych. W niektórych tekstach multigrafy nazywane są po prostu grafami.

Czasami grafy mogą zawierać pętle , które są krawędziami łączącymi wierzchołek z samym sobą. Za umożliwienie pętle, powyższa definicja musi zostać zmieniona poprzez zdefiniowanie krawędzie jak multisets dwóch wierzchołków zamiast dwóch zestawów. Takie uogólnione grafy nazywane są grafami z pętlami lub po prostu grafami, gdy z kontekstu jasno wynika, że ​​pętle są dozwolone.

Ogólnie rzecz biorąc, zbiór wierzchołków V ma być skończony; oznacza to, że zbiór krawędzi jest również skończony. Czasami rozważa się grafy nieskończone , ale częściej traktuje się je jako szczególny rodzaj relacji binarnej , ponieważ większość wyników na grafach skończonych nie rozciąga się na przypadek nieskończony lub wymaga raczej innego dowodu.

Pusty wykres jest wykresem, który ma pusty zbiór wierzchołków (a więc zbiór pusty krawędzi). Zamówienie wykresu jest jego ilość wierzchołków | V | . Wielkość wykresu jest jego liczba krawędzi | E | . Jednak w niektórych kontekstach, takich jak wyrażanie złożoności obliczeniowej algorytmów, rozmiar wynosi | V | + | E | (w przeciwnym razie niepusty wykres mógłby mieć rozmiar 0). Stopień lub wartościowość z wierzchołkiem jest ilość krawędzi, które pada na nią; dla wykresów z pętlami pętla jest liczona dwukrotnie.

Na grafie rzędu n maksymalny stopień każdego wierzchołka wynosi n − 1 (lub n, jeśli dozwolone są pętle), a maksymalna liczba krawędzi to n ( n − 1)/2 (lub n ( n + 1)/ 2, jeśli pętle są dozwolone).

Krawędzie grafu definiują symetryczną relację na wierzchołkach, zwaną relacją sąsiedztwa . W szczególności, dwa wierzchołki x i y są w sąsiedztwie , czy { x , y } jest krawędzią. Wykres może być w pełni określony przez macierz sąsiedztwa A , która jest macierzą kwadratową, gdzie A _ij określa liczbę połączeń od wierzchołka i do wierzchołka j . Tymczasem dla prostego wykresu , wskazującego odpowiednio rozłączenie lub połączenie (to znaczy, że krawędź nie może zaczynać się i kończyć w tym samym wierzchołku). Wykresy z pętlami własnymi będą charakteryzowane przez niektóre lub wszystkie wartości dodatniej liczby całkowitej, a multigrafy (z wieloma krawędziami między wierzchołkami) będą charakteryzowane przez niektóre lub wszystkie wartości dodatnich liczb całkowitych. Grafy nieskierowane będą miały symetryczną macierz sąsiedztwa ( ). ${\displaystyle n\razy n}$${\ Displaystyle A_ {ij} \ w \ {0,1 \}}$${\ Displaystyle A_ {ii} = 0}$${\ Displaystyle A_ {ii}}$${\ Displaystyle A_ {ij}}$${\ Displaystyle A_ {ij} = A_ {ji}}$

Kierowany wykres

Wykres skierowany z trzema wierzchołkami i czterema skierowanymi krawędziami (podwójna strzałka reprezentuje krawędź w każdym kierunku).

Skierowane wykres lub digrafu jest wykres, w którym krawędzie mają orientacje.

W jednym ograniczonym, ale bardzo powszechnym znaczeniu tego terminu, graf skierowany to para składająca się z: ${\ Displaystyle G = (V, E)}$

• ${\ Displaystyle V}$, A set of wierzchołków (zwane również węzły lub punkty );
• ${\ Displaystyle E \ subseteq \ {(x, y) \ mid (x, y) \ w V ^ {2} \; {\ textrm {i}} \; x \ neq y \}}$, A set of krawędzi (zwane również skierowane krawędzie , skierowane linki , skierowane linie , strzałki lub łuki ), które są uporządkowane pary wierzchołków (to jest krawędź jest związane z dwoma odrębnymi wierzchołków).

Aby uniknąć niejasności, tego typu obiekt można nazwać właśnie skierowanym grafem prostym .

Na brzegu skierowany od celu , wierzchołki i są nazywane punktów końcowych krawędzi, tylnych krawędzi i głowicy krawędzi. Krawędź mówi się połączyć i i być przypadek w i . Wierzchołek może istnieć w grafie i nie należeć do krawędzi. Krawędź jest nazywany odwróconym krawędź o . Wielokrotne krawędzie , niedozwolone w powyższej definicji, to dwie lub więcej krawędzi z tym samym ogonem i tą samą głową. ${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (y,x)}$${\displaystyle (x,y)}$

W jednym bardziej ogólnym znaczeniu terminu dopuszczającego wiele krawędzi, graf skierowany jest uporządkowaną trójką zawierającą: ${\ Displaystyle G = (V, E, \ phi )}$

• ${\ Displaystyle V}$, A set of wierzchołków (zwane również węzły lub punkty );
• ${\ Displaystyle E}$, A set of krawędzi (nazywanych także skierowanych krawędziach , ukierunkowane łącza , skierowanych linii , strzałek lub łuki );
• ${\ Displaystyle \ phi: E \ do \ {(x, y) \ mid (x, y) \ w V ^ {2} \; {\ textrm {i}} \; x \ neq r \}}$, funkcja incydentu mapująca każdą krawędź do uporządkowanej pary wierzchołków (to znaczy, że krawędź jest powiązana z dwoma różnymi wierzchołkami).

Aby uniknąć niejasności, tego typu obiekt można nazwać właśnie multigrafem skierowanym .

Pętla ma krawędź, która łączy wierzchołek do siebie. Grafy skierowane, jak zdefiniowano w dwóch powyższych definicjach, nie mogą mieć pętli, ponieważ pętla łącząca wierzchołek z samym wierzchołkiem jest krawędzią (dla prostego grafu skierowanego) lub jest przypadkowa (dla multigrafu skierowanego), która nie znajduje się w . Aby więc dopuścić pętle, definicje muszą zostać rozszerzone. W przypadku prostych grafów skierowanych należy zmienić definicję na . W przypadku multigrafów skierowanych należy zmienić definicję na . Aby uniknąć niejasności, tego typu obiekty można nazwać odpowiednio skierowanym prostym grafem przepuszczającym pętle i skierowanym multigrafem przepuszczającym pętle (lub kołczanem ). ${\displaystyle x}$${\displaystyle (x,x)}$${\ Displaystyle \ {(x, y) \ mid (x, y) \ w V ^ {2} \; {\ textrm {i}} \; x \ neq r \}}$${\ Displaystyle E}$${\ Displaystyle E \ subseteq \ {(x, y) \ mid (x, y) \ w V ^ {2} \}}$${\displaystyle \phi}$${\ Displaystyle \ phi: E \ do \ {(x, y) \ mid (x, y) \ w V ^ {2} \}}$

Krawędzie skierowanego prosty wykres umożliwiający pętli jest jednorodny związek ~ w wierzchołkach , które są nazywane w związku przylegania z . W szczególności, dla każdej krawędzi , jej punkty końcowe i są uważane za sąsiadujące ze sobą, co jest oznaczone jako ~ . ${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

Wykres mieszany

Miesza wykres przedstawia wykres, w którym niektóre krawędzie mogą być kierowane, a niektóre mogą być nieukierunkowane. Jest to uporządkowana potrójna G = ( V , E , A ) dla mieszanego prostego grafu i G = ( V , E , A , ϕ _E , ϕ _A ) dla mieszanego multigrafu z V , E (nieskierowane krawędzie), A (krawędzie skierowane), ϕ _E i ϕ _A zdefiniowane jak wyżej. Grafy skierowane i nieskierowane to przypadki szczególne.

Wykres ważony

Wykres ważony z dziesięcioma wierzchołkami i dwunastoma krawędziami.

Ważona wykres lub sieć jest wykres, w którym ilość (masa) jest przypisana do każdej krawędzi. Takie wagi mogą reprezentować na przykład koszty, długości lub pojemności, w zależności od danego problemu. Takie wykresy pojawiają się w wielu kontekstach, na przykład w problemach najkrótszych ścieżek, takich jak problem komiwojażera .

Rodzaje wykresów

Wykres zorientowany

Jedną z definicji grafu zorientowanego jest to, że jest to graf skierowany, w którym co najwyżej jeden z ( x , y ) i ( y , x ) może być krawędziami grafu. Oznacza to, że jest to graf skierowany, który można utworzyć jako orientację grafu nieskierowanego (prostego).

Niektórzy autorzy używają „wykresu zorientowanego” w znaczeniu „wykresu ukierunkowanego”. Niektórzy autorzy używają „grafu zorientowanego” na określenie dowolnej orientacji danego grafu nieskierowanego lub multigrafu.

Zwykły wykres

Graf regularny jest wykresem, w którym każdy wierzchołek ma taką samą liczbę sąsiadów, czyli każdy wierzchołek ma ten sam stopień. Wykres regularny o wierzchołkach stopnia k nazywany jest grafem regularnym k lub wykresem regularnym stopnia k .

Kompletny wykres

Kompletny wykres z pięcioma wierzchołkami i dziesięcioma krawędziami. Każdy wierzchołek ma krawędź do każdego innego wierzchołka.

Zakończeniu wykres przedstawia wykres, w którym każda para wierzchołków jest połączona przez krawędź. Kompletny wykres zawiera wszystkie możliwe krawędzie.

Wykres skończony

Skończonych wykres przedstawia wykres na którym zestaw wierzchołek oraz zestaw krawędzi są skończone zestawy . W przeciwnym razie nazywa się to grafem nieskończonym .

Najczęściej w teorii grafów zakłada się, że omawiane grafy są skończone. Jeśli wykresy są nieskończone, zwykle jest to wyraźnie powiedziane.

Połączony wykres

W grafie nieskierowanym nieuporządkowana para wierzchołków { x , y } jest nazywana połączonymi, jeśli ścieżka prowadzi z x do y . W przeciwnym razie para nieuporządkowana jest nazywana odłączony .

Połączony wykres jest nieukierunkowane wykres, który jest połączony z co nieuporządkowane parę wierzchołków grafu. W przeciwnym razie nazywa się to grafem rozłączonym .

W grafie skierowanym uporządkowaną parę wierzchołków ( x , y ) nazywamy silnie połączonymi, jeśli skierowana ścieżka prowadzi z x do y . W przeciwnym razie uporządkowaną parę nazywamy słabo połączoną, jeśli nieskierowana ścieżka prowadzi od x do y po zastąpieniu wszystkich jej skierowanych krawędzi krawędziami nieskierowanymi. W przeciwnym razie uporządkowana para nazywana jest rozłączona .

Mocno połączony wykres jest skierowany wykres, w którym każdy uporządkowane pary wierzchołków grafu jest silnie połączone. W przeciwnym razie nazywa się to grafem słabo połączonym, jeśli każda uporządkowana para wierzchołków w grafie jest słabo związana. W przeciwnym razie nazywa się to grafem rozłączonym .

K wierzchołek połączone wykres lub k krawędzi połączony wykres jest wykres, który ma zestaw k - 1 istnieje wierzchołki (odpowiednio brzegi) tak, że po usunięciu odłącza wykres. K -Vertex podłączonego wykres jest często nazywany po prostu k-spójny graf .

Wykres dwudzielny

Dwudzielny wykres jest prosty wykres w którym zestaw wierzchołek może być podzielona na dwie grupy, W i X , tak, że żadne dwa wierzchołki W współdzielą wspólny krawędzi i ma dwa wierzchołki X mają wspólną krawędź. Alternatywnie jest to wykres o liczbie chromatycznej 2.

W kompletnym grafie dwudzielnym zbiór wierzchołków jest sumą dwóch rozłącznych zbiorów, W i X , tak że każdy wierzchołek w W sąsiaduje z każdym wierzchołkiem w X, ale nie ma krawędzi w W ani X .

Wykres ścieżki

Wykres ścieżki lub liniowy wykres porządku n ≥ 2 przedstawia wykres, w którym wierzchołki mogą być wyświetlane w kolejności v ₁ , V, ₂ , ..., v _n , tak że krawędzie są { V _i , v _{i + 1} } , gdzie i = 1, 2, …, n − 1. Wykresy ścieżki można scharakteryzować jako grafy połączone, w których stopień wszystkich wierzchołków z wyjątkiem dwóch wynosi 2, a stopień dwóch pozostałych wierzchołków wynosi 1. Jeśli graf ścieżki występuje jako podgraf innego wykresu, jest to ścieżka w tym wykresie.

Wykres planarny

Płaska wykres przedstawia wykres, którego wierzchołki oraz krawędzie mogą być sporządzone w płaszczyźnie tak, że żadne dwie krawędzie przecinają.

Wykres cyklu

Wykres cyklu lub okrągły wykres porządku n ≥ 3 przedstawia wykres, w którym wierzchołki mogą być wyświetlane w kolejności v ₁ , V, ₂ , ..., v _n , tak że krawędzie są { V _i , v _{i + 1} } , gdzie i = 1, 2, …, n − 1, plus krawędź { v _n , v ₁ } . Wykresy cyklu można scharakteryzować jako połączone wykresy, w których stopień wszystkich wierzchołków wynosi 2. Jeśli wykres cyklu występuje jako podgraf innego wykresu, jest to cykl lub obwód na tym wykresie.

Drzewo

Drzewo jest nieukierunkowane wykres, w którym każde dwa wierzchołki są połączone dokładnie jedną ścieżką , lub równoważnie podłączonego acykliczny undirected wykresu.

Las jest nieukierunkowane wykres, w którym dowolne dwa wierzchołki są połączone za pomocą co najwyżej jedną ścieżkę, lub równoważnie acyklicznego nieukierunkowane wykresu lub równoważnie suma rozłączna drzew.

Polytree

Polytree (lub skierowane drzewa lub zorientowane drzewa lub pojedynczo połączone w sieci ) jest skierowany acykliczny wykres (DAG), których leżące u nieukierunkowane wykresu drzewa.

Polyforest (lub skierowane lasu lub zorientowane las ) jest skierowany acykliczny wykres którego bazowego nieukierunkowane wykresu las.

Klasy zaawansowane

Bardziej zaawansowane rodzaje wykresów to:

• Wykres Petersena i jego uogólnienia;
• doskonałe wykresy ;
• kopie ;
• wykresy akordowe ;
• inne grafy z dużymi grupami automorfizmów : grafy wierzchołkowo-przechodnie , łukowo-przechodnie i odległościowo-przechodnie ;
• grafy silnie regularne i ich uogólnienia grafy odległościowe .

Własności grafów

Dwie krawędzie grafu nazywane są sąsiadującymi, jeśli mają wspólny wierzchołek. Dwie krawędzie grafu skierowanego nazywamy kolejnymi, jeśli głowa pierwszego jest ogonem drugiego. Podobnie, dwa wierzchołki nazywane są sąsiadującymi, jeśli mają wspólną krawędź ( kolejne, jeśli pierwszy jest ogonem, a drugi jest głową krawędzi), w którym to przypadku mówi się, że wspólna krawędź łączy dwa wierzchołki. Krawędź i wierzchołek na tej krawędzi nazywane są incydentem .

Wykres z tylko jednym wierzchołkiem i bez krawędzi nazywany jest grafem trywialnym . Graf z samymi wierzchołkami i bez krawędzi jest znany jako graf bez krawędzi . Graf bez wierzchołków i krawędzi jest czasami nazywany grafem zerowym lub grafem pustym , ale terminologia nie jest spójna i nie wszyscy matematycy dopuszczają ten obiekt.

Normalnie wierzchołki grafu, jako elementy zbioru, są rozróżnialne. Ten rodzaj wykresu można nazwać vertex-labeled . Jednak w przypadku wielu pytań lepiej traktować wierzchołki jako nie do odróżnienia. (Oczywiście wierzchołki mogą być nadal rozróżnialne na podstawie właściwości samego grafu, np. po liczbie krawędzi przypadających na siebie.) Te same uwagi dotyczą krawędzi, więc grafy z krawędziami etykietowanymi nazywamy krawędziami etykietowanymi . Wykresy z etykietami przyczepionymi do krawędzi lub wierzchołków są ogólnie określane jako oznaczone . W związku z tym grafy, w których nie można rozróżnić wierzchołków i krawędzi, nazywamy grafami unlabeled . (W literaturze termin „ etykietowany” może odnosić się do innych rodzajów etykietowania, poza tym, które służy jedynie do rozróżniania różnych wierzchołków lub krawędzi.)

Kategoria wszystkich wykresach jest kategoria przecinek Set ↓ D , gdzie D : Set → Set jest funktor biorąc zestaw s do s × s .

Przykłady

Wykres z sześcioma wierzchołkami i siedmioma krawędziami.

• Diagram jest schematyczną reprezentacją grafu z wierzchołkami i krawędziami${\ Displaystyle V = \ {1,2,3,4,5,6\}}$${\ Displaystyle E = \ {\ {1,2 \}, \ {1,5 \}, \ {2,3 \}, \ {2,5 \}, \ {3,4 \}, \ {4 ,5\},\{4,6\}\}.}$
• W informatyce grafy skierowane są używane do reprezentowania wiedzy (np. graf pojęciowy ), automatów skończonych i wielu innych struktur dyskretnych.
• Binarny stosunek R na zbiorze X wyznacza skierowaną wykres. Element x z X jest bezpośrednim poprzednikiem elementu y z X wtedy i tylko wtedy, gdy xRy .
• Wykres skierowany może modelować sieci informacyjne, takie jak Twitter , w których jeden użytkownik podąża za drugim.
• Szczególnie regularnymi przykładami grafów skierowanych są grafy Cayleya grup skończenie generowanych, a także grafy Coset Schreiera
• W teorii kategorii każda mała kategoria ma leżący pod nią multigraf skierowany, którego wierzchołki są obiektami kategorii, a krawędzie są strzałkami kategorii. W języku teorii kategorii mówi się, że istnieje funktor zapominania z kategorii małych kategorii do kategorii kołczanów .

Operacje na wykresach

Istnieje kilka operacji, które tworzą nowe wykresy z początkowych, które można zaklasyfikować do następujących kategorii:

• operacje jednoargumentowe , które tworzą nowy graf z początkowego, takie jak:
  • skurcz krawędzi ,
  • wykres liniowy ,
  • wykres podwójny ,
  • wykres dopełnienia ,
  • przepisywanie wykresów ;
• operacje binarne , które tworzą nowy graf z dwóch początkowych, takich jak:
  • rozłączny związek grafów ,
  • iloczyn kartezjański wykresów ,
  • iloczyn tensorowy wykresów ,
  • silny iloczyn wykresów ,
  • iloczyn leksykograficzny wykresów ,
  • wykresy szeregowo-równoległe .

Uogólnienia

W hipergrafie krawędź może łączyć więcej niż dwa wierzchołki.

Graf nieskierowany może być postrzegany jako kompleks symplicjalny składający się z 1- simpliców (krawędzie) i 0-simpliców (wierzchołki). Jako takie, kompleksy są uogólnieniami grafów, ponieważ pozwalają na uproszczenia wyższych wymiarów.

Każdy wykres daje początek matroidowi .

W teorii modeli graf jest tylko strukturą . Ale w tym przypadku nie ma ograniczeń co do liczby krawędzi: może to być dowolna liczba kardynalna , patrz wykres ciągły .

W biologii obliczeniowej , analiza wykres mocy przedstawia wykres mocy jako alternatywne przedstawienie nieukierunkowane wykresów.

W systemów informacji geograficznej , sieci geometrycznej ściśle wzorowane na wykresach i pożyczać wiele koncepcji z teorii wykres wykonać analizę przestrzenną dróg lub sieciach energetycznych.

Zobacz też

• Wykres koncepcyjny
• Wykres (abstrakcyjny typ danych)
• Baza wykresów
• Rysowanie wykresu
• Lista tematów teorii grafów
• Lista publikacji z teorii grafów
• Teoria sieci

Uwagi

Bibliografia

• Balakrishnan, VK (1997). Teoria grafów (wyd. 1). McGraw-Hill. Numer ISBN 978-0-07-005489-9.
• Bang-Jensen, J.; Gutin, G. (2000). Dwuznaki: teoria, algorytmy i zastosowania . Skoczek.
• Bender, Edward A.; Williamson, S. Gill (2010). Listy, decyzje i wykresy. Z wprowadzeniem do prawdopodobieństwa .
• Berge, Claude (1958). Aplikacje Théorie des graphes et ses (w języku francuskim). Paryż: Dunod.
• Biggsa, Normana (1993). Teoria grafów algebraicznych (wyd. 2). Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-45897-9.
• Bollobás, Bela (2002). Nowoczesna teoria grafów (wyd. 1). Skoczek. Numer ISBN 978-0-387-98488-9.
• Diestel, Reinhard (2005). Teoria grafów (3rd ed.). Berlin, Nowy Jork: Springer-Verlag. Numer ISBN 978-3-540-26183-4.
• Graham, RL; Grötschel, M.; Lovász, L. (1995). Podręcznik kombinatoryki . MIT Naciśnij. Numer ISBN 978-0-262-07169-7.
• Gross, Jonathan L.; Yellen, Jay (1998). Teoria grafów i jej zastosowania . CRC Prasa. Numer ISBN 978-0-8493-3982-0.
• Gross, Jonathan L.; Yellen, Jay (2003). Podręcznik teorii grafów . CRC. Numer ISBN 978-1-58488-090-5.
• Harary, Frank (1995). Teoria grafów . Wydawnictwo Addisona Wesleya. Numer ISBN 978-0-201-41033-4.
• Iyanaga, Shokichi; Kawada, Yukiyosi (1977). Encyklopedyczny słownik matematyki . MIT Naciśnij. Numer ISBN 978-0-262-09016-2.
• Zwillinger, Daniel (2002). CRC Standardowe Tabele Matematyczne i Wzory (wyd. 31.). Chapman & Hall/CRC. Numer ISBN 978-1-58488-291-6.

Dalsza lektura

• Trudeau, Richard J. (1993). Wprowadzenie do teorii grafów (poprawiona, rozszerzona republikacja. ed.). Nowy Jork: Dover Publikacje . Numer ISBN 978-0-486-67870-2. Źródło 8 sierpnia 2012 .

Zewnętrzne linki

• Multimedia związane z Graph (matematyka dyskretna) w Wikimedia Commons
• Weisstein, Eric W. "Wykres" . MatematykaŚwiat .