Zakorzeniony wykres
W matematyce , aw szczególności w teorii grafów , grafem ukorzenionym jest graf , w którym jako pierwiastek wyróżniono jeden wierzchołek. Zbadano zarówno skierowane , jak i nieskierowane wersje grafów ukorzenionych, a także istnieją warianty definicji, które pozwalają na wiele pierwiastków.
Wykresy ukorzenione mogą być również znane (w zależności od ich zastosowania) jako wykresy punktowe lub wykresy przepływowe . W niektórych zastosowaniach tych grafów istnieje dodatkowy wymóg, aby cały graf był osiągalny z wierzchołka korzenia.
Wariacje
W teorii grafów topologicznych pojęcie grafu ukorzenionego można rozszerzyć, aby traktować wiele wierzchołków lub wiele krawędzi jako pierwiastki. Te pierwsze są czasami nazywane grafami zakorzenionymi w wierzchołkach, aby odróżnić je od grafów zakorzenionych na krawędzi w tym kontekście. Grafy z wieloma węzłami wyznaczonymi jako pierwiastki są również przedmiotem zainteresowania kombinatoryki w obszarze grafów losowych . Grafy te są również nazywane grafami z wieloma korzeniami .
Terminy zakorzeniony graf skierowany lub zakorzeniony dwuznak również widzą różnice w definicjach. Oczywistym przeszczepem jest rozważenie zakorzenionego digrafu poprzez zidentyfikowanie określonego węzła jako korzenia. Jednak w informatyce terminy te zwykle odnoszą się do węższego pojęcia, a mianowicie ukorzeniony graf skierowany jest digrafem z wyróżnionym węzłem r , tak że istnieje skierowana ścieżka od r do dowolnego węzła innego niż r . Autorzy, którzy podają bardziej ogólną definicję, mogą nazywać je połączonymi ukorzenionymi dwuznakami lub dostępne ukorzenione grafy (patrz § Teoria mnogości ).
Sztuka programowania komputerowego definiuje digrafy ukorzenione nieco szerzej, a mianowicie graf skierowany nazywany jest ukorzenionym, jeśli ma co najmniej jeden węzeł, który może dotrzeć do wszystkich pozostałych węzłów; Knuth zauważa, że tak zdefiniowane pojęcie jest swego rodzaju środkiem pośrednim między pojęciami silnie połączonego i połączonego digrafu .
Aplikacje
Wykresy przepływu
W informatyce grafy ukorzenione, w których wierzchołek główny może sięgać wszystkich innych wierzchołków, nazywane są grafami przepływu lub grafami przepływu . Czasami dodaje się dodatkowe ograniczenie określające, że wykres przepływu musi mieć również jeden wierzchołek wyjściowy ( ujście ).
Grafy przepływu można postrzegać jako abstrakcje schematów blokowych , z usuniętymi elementami niestrukturalnymi (zawartość i typy węzłów). Być może najbardziej znaną podklasą grafów przepływu są grafy kontrolno-przepływowe , używane w kompilatorach i analizie programów . Dowolny wykres przepływu można przekształcić w wykres przepływu kontrolnego, wykonując skrócenie krawędzi na każdej krawędzi, która jest jedyną krawędzią wychodzącą z jego źródła i jedyną krawędzią przychodzącą do celu. Innym powszechnie używanym rodzajem wykresu przepływu jest wykres wywołań , w którym węzły odpowiadają całym podprogramom .
Ogólne pojęcie wykresu przepływu nazwano wykresem programu , ale ten sam termin był również używany do określenia tylko wykresów przepływu sterowania. Grafy przepływu nazywane są także nieoznaczonymi grafami przepływu i właściwymi grafami przepływu . Te wykresy są czasami używane w testowaniu oprogramowania .
Gdy wymagane jest jedno wyjście, grafy przepływu mają dwie właściwości, które nie są ogólnie wspólne z grafami skierowanymi. Grafy przepływu mogą być zagnieżdżane, co jest odpowiednikiem wywołania podprogramu (chociaż nie ma pojęcia przekazywania parametrów), a grafy przepływu można również sekwencjonować, co jest odpowiednikiem sekwencyjnego wykonywania dwóch fragmentów kodu. Pierwsze grafy przepływu są definiowane jako grafy przepływu, których nie można rozłożyć poprzez zagnieżdżanie lub sekwencjonowanie przy użyciu wybranego wzoru podgrafów, na przykład prymitywów programowania strukturalnego . Przeprowadzono badania teoretyczne nad określeniem np. proporcji głównych grafów przepływu dla wybranego zestawu grafów.
Teoria mnogości
Peter Aczel użył ukorzenionych grafów skierowanych, tak że każdy węzeł jest osiągalny z korzenia (który nazywa dostępnymi grafami spiczastymi ), aby sformułować aksjomat antypodstawowy Aczela w nieuzasadnionej teorii mnogości . W tym kontekście każdy wierzchołek dostępnego wykresu spiczastego modeluje zbiór (nieuzasadniony) w ramach teorii mnogości Aczela (nieuzasadniony), a łuk od wierzchołka v do wierzchołka w modeluje , że v jest elementem z w . Aksjomat antyfundamentacyjny Aczela stwierdza, że każdy dostępny graf spiczasty modeluje w ten sposób rodzinę (nieuzasadnionych) zbiorów.
Teoria gier kombinatorycznych
Biorąc pod uwagę czysto kombinatoryczną grę , istnieje powiązany ukorzeniony graf skierowany, którego wierzchołki są pozycjami w grze, a krawędzie są ruchami, a przechodzenie grafu począwszy od korzenia służy do tworzenia drzewa gry . Jeśli wykres zawiera skierowane cykle , to pozycja w grze może powtarzać się nieskończenie wiele razy, a reguły są zwykle potrzebne, aby zapobiec kontynuowaniu gry w nieskończoność. W przeciwnym razie graf jest skierowanym grafem acyklicznym , a jeśli nie jest to drzewo z korzeniami , gra ma transpozycje . Ten graf i jego topologia są ważne w badaniu złożoności gier , gdzie złożoność przestrzeni stanów to liczba wierzchołków grafu, a średnia długość gry to średnia liczba wierzchołków przechodzących od korzenia do wierzchołka bez bezpośrednich następców , a średni czynnik rozgałęzienia drzewa gry to średni stopień zewnętrzny grafu.
Wyliczanie kombinatoryczne
Liczba ukorzenionych nieskierowanych grafów dla 1, 2, ... węzłów wynosi 1, 2, 6, 20, 90, 544, ... (sekwencja A000666 w OEIS )
Pojęcia pokrewne
Szczególnym przypadkiem zainteresowania są drzewa ukorzenione , drzewa z wyróżnionym wierzchołkiem korzenia. Jeśli skierowane ścieżki od korzenia w ukorzenionym dwuznaku są dodatkowo ograniczone, aby były unikalne, wówczas otrzymane pojęcie jest pojęciem (ukorzenionego) drzewiastego - odpowiednika ukorzenionego drzewa w grafie skierowanym. Ukorzeniony wykres zawiera drzewostan z tym samym korzeniem wtedy i tylko wtedy, gdy cały wykres może być osiągnięty z korzenia, a informatycy badali algorytmiczne problemy znajdowania optymalnych drzew.
Ukorzenione wykresy można łączyć za pomocą ukorzenionego iloczynu grafów .
Zobacz też
Dalsza lektura
- McMahon, Elizabeth W. (1993), „O wielomianie greedoidalnym dla ukorzenionych grafów i ukorzenionych dwuznaków”, Journal of Graph Theory , 17 (3): 433–442, doi : 10,1002 / jgt.3190170316
- Gordon, Gary (2001), „Charakterystyczny wielomian dla ukorzenionych grafów i ukorzenionych digrafów”, Discrete Mathematics , 232 (1–3): 19–33, doi : 10,1016 / S0012-365X (00) 00186-2