Wierzchołek (teoria grafów)
W matematyce dyskretnej , a dokładniej w teorii grafów , wierzchołek (liczba mnoga wierzchołków ) lub węzeł jest podstawową jednostką, z której tworzone są grafy: graf nieskierowany składa się ze zbioru wierzchołków i zbioru krawędzi ( nieuporządkowanych par wierzchołków), podczas gdy graf skierowany składa się ze zbioru wierzchołków i zbioru łuków (uporządkowanych par wierzchołków). Na diagramie wykresu wierzchołek jest zwykle reprezentowany przez okrąg z etykietą, a krawędź jest reprezentowana przez linię lub strzałkę rozciągającą się od jednego wierzchołka do drugiego.
Z punktu widzenia teorii grafów wierzchołki są traktowane jako obiekty niepodzielne i niepodzielne , chociaż mogą mieć dodatkową strukturę w zależności od aplikacji, z której graf pochodzi; na przykład sieć semantyczna to graf, w którym wierzchołki reprezentują pojęcia lub klasy obiektów.
Mówi się, że dwa wierzchołki tworzące krawędź są punktami końcowymi tej krawędzi, a krawędź jest incydentna z wierzchołkami. Mówimy, że wierzchołek w sąsiaduje z innym wierzchołkiem v , jeśli graf zawiera krawędź ( v , w ). Sąsiedztwo wierzchołka v jest indukowanym podgrafem grafu, utworzonym przez wszystkie wierzchołki sąsiadujące z v .
Rodzaje wierzchołków
Stopień wierzchołka, oznaczony 𝛿(v) w grafie , to liczba krawędzi do niego incydentnych. Izolowany wierzchołek to wierzchołek o stopniu zerowym; to znaczy wierzchołek, który nie jest punktem końcowym żadnej krawędzi (przykładowy obraz ilustruje jeden izolowany wierzchołek). Wierzchołek liścia (również wierzchołek wiszący ) to wierzchołek o stopniu pierwszym. W grafie skierowanym można wyróżnić stopień wyjściowy (liczba krawędzi wychodzących), oznaczony 𝛿 + (v), od stopnia wejściowego (liczba krawędzi przychodzących), oznaczony 𝛿 − (v); wierzchołek źródłowy jest wierzchołkiem o stopniu wejściowym zero, podczas gdy wierzchołek ujścia jest wierzchołkiem o stopniu zewnętrznym zero. Uproszczony wierzchołek to taki, którego sąsiedzi tworzą klikę : co dwóch sąsiadów sąsiaduje. Wierzchołek uniwersalny to wierzchołek, który sąsiaduje z każdym innym wierzchołkiem grafu.
Wycięty wierzchołek to wierzchołek, którego usunięcie spowodowałoby rozłączenie pozostałego wykresu; separator wierzchołków to zbiór wierzchołków, których usunięcie spowodowałoby rozdzielenie pozostałego grafu na małe części. Graf połączony k-wierzchołkami to graf, w którym usunięcie mniej niż k wierzchołków zawsze pozostawia pozostały graf połączony. Niezależny zbiór to zbiór wierzchołków, z których żadne dwa nie sąsiadują ze sobą, a pokrycie wierzchołków to zbiór wierzchołków, który zawiera co najmniej jeden punkt końcowy każdej krawędzi grafu. Przestrzeń wierzchołków wykresu to przestrzeń wektorowa mająca zbiór wektorów bazowych odpowiadających wierzchołkom grafu.
Graf jest wierzchołkowo przechodni, jeśli ma symetrie, które odwzorowują dowolny wierzchołek na dowolny inny wierzchołek. W kontekście wyliczania grafów i izomorfizmu grafów ważne jest rozróżnienie wierzchołków oznaczonych i nieoznakowanych . Oznaczony wierzchołek to wierzchołek powiązany z dodatkowymi informacjami, które umożliwiają odróżnienie go od innych oznaczonych wierzchołków; dwa grafy można uznać za izomorficzne tylko wtedy, gdy zgodność między ich wierzchołkami tworzy pary wierzchołków z równymi etykietami. Nieoznaczony wierzchołek to taki, który można zastąpić dowolnym innym wierzchołkiem tylko na podstawie jego wierzchołka przylegania na wykresie i nie opiera się na żadnych dodatkowych informacjach.
Wierzchołki w grafach są analogiczne, ale nie tożsame z wierzchołkami wielościanów : szkielet wielościanu tworzy graf, którego wierzchołki są wierzchołkami wielościanu, ale wierzchołki wielościanu mają dodatkową strukturę (ich położenie geometryczne), to jest zakłada się, że nie występuje w teorii grafów. Figura wierzchołka wierzchołka w wielościanie jest analogiczna do sąsiedztwa wierzchołka w grafie.
Zobacz też
- Gallo, Giorgio; Pallotyno Stefano (1988). „Algorytmy najkrótszej ścieżki”. Roczniki badań operacyjnych . 13 (1): 1–79. doi : 10.1007/BF02288320 . S2CID 62752810 .
- Berge, Claude , Théorie des graphes et ses Applications . Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 s. (wydanie angielskie, Wiley 1961; Methuen & Co, New York 1962; rosyjski, Moskwa 1961; hiszpański, Meksyk 1962; rumuński, Bukareszt 1969; chiński, Szanghaj 1963 ; Drugi druk pierwszego wydania angielskiego z 1962 r. Dover, New York 2001)
- Chartrand, Gary (1985). Wstępna teoria grafów . Nowy Jork: Dover. ISBN 0-486-24775-9 .
- Biggs, Norman; Lloyd, EH; Wilson, Robin J. (1986). Teoria grafów, 1736-1936 . Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9 .
- Harary, Frank (1969). Teoria grafów . Czytanie, Massachusetts: Addison-Wesley Publishing. ISBN 0-201-41033-8 .
- Harary, Frank; Palmer, Edgar M. (1973). Wyliczanie graficzne . Nowy Jork, prasa akademicka. ISBN 0-12-324245-2 .