Obiekt Graph - Graph property

Przykładowy wykres, z właściwościami są płaskie i są połączone , oraz z rzędu 6, powierzchnia 7, o średnicy 3 obwodowego 3 połączeń wierzchołek 1 i sekwencji stopień <3, 3, 3, 2, 2, 1>

W teorii wykres , A właściwość wykres lub wykres niezmienna jest właściwością wykresów , który zależy jedynie od abstrakcyjnej struktury, a nie w reprezentacji wykres jako poszczególne labellings lub rysunków wykresu.

definicje

Rysując wykres i wykres reprezentacja są ważne zagadnienia z teorii grafów, w celu skoncentrowania się tylko na abstrakcyjnej struktury grafów, o właściwość wykresu określa się właściwość zachowana we wszystkich możliwych isomorphisms wykresu. Innymi słowy, jest to własność samego wykresu, a nie konkretnej reprezentacji rysunku lub wykresu. Nieformalnie określenie „wykres niezmienne” stosowane jest dla właściwości wyrażona ilościowo, a „nieruchomy” odnosi się zwykle na opisowy charakteryzacji wykresów. Na przykład stwierdzenie „wykres nie ma wierzchołki stopnia 1” to „własność”, podczas gdy „liczba wierzchołków stopnia 1 w postaci wykresu” jest „niezmienne”.

Bardziej formalnie, właściwość wykres jest klasą wykresów z własności, że dowolne dwa izomorficzne wykresy albo oba należą do klasy, lub oba nie należą do niego. Równoważnie, właściwość wykresu mogą być zawarte stosując funkcję wskaźnika klasy, funkcję z wykresy wartości logiczne, które odnosi się do wykresów z klasy i fałszywie w inny sposób; znowu jakieś dwa grafy izomorficzne musi mieć taką samą wartość funkcji jak każdy inny. Wykres niezmienna lub wykres parametrów mogą być podobnie sformalizowane jako funkcja na podstawie wykresów do szerszej klasy wartości, na przykład w postaci liczb całkowitych, liczb rzeczywistych , sekwencji liczb, lub wielomianów , które z kolei ma tę samą wartość dla dwóch dowolnych izomorficznych wykresów.

Właściwości właściwości

Wiele właściwości grafów są dobrze wychowane w odniesieniu do pewnych naturalnych zamówień częściowych lub przedsprzedaży określonych na wykresach:

  • Właściwość wykres P jest dziedziczną , jeśli każdy wywołane subgraph wykresu usytuowanych P posiada własności P . Na przykład, będący idealnym wykres albo być cięciwy wykres są właściwości dziedziczne.
  • Właściwość wykres jest monotonia , jeśli każdy subgraph wykresu z własności P posiada również właściwości P . Na przykład, będący dwudzielny wykres albo być trójkątny wolny wykres jest monotoniczne. Każda nieruchomość monotonia jest dziedziczna, ale niekoniecznie na odwrót; Na przykład subgraphs z akordowych wykresach nie są koniecznie cięciwy, więc jest do cięciwy przebieg nie jest monotoniczne.
  • Właściwość wykres jest drobne zamknięte jeśli każdy wykres drobne wykresu usytuowanych P posiada własności P . Na przykład, będąc płaską wykres jest niewielki zamknięty. Każda nieruchomość moll zamknięty jest monotonia, ale niekoniecznie na odwrót; na przykład, nieletnich trójkąta wolne wykresach nie muszą same trójkątne darmo.

Definicje te mogą być inne od właściwości, które mają invarianty liczbowych wykresy: a niezmienne wykres jest dziedziczną, monotoniczne albo drobne zamknięty, gdy funkcja formalizing niezmiennego tworzy monotoniczny funkcyjne z odpowiednich porządek częściowy na wykresach do liczb rzeczywistych.

Dodatkowo, niezmienniki wykres badano pod względem ich zachowania w odniesieniu do suma rozłączna wykresów:

  • Wykres niezmienna jest dodatek , jeżeli dla wszystkich dwóch wykresów G i H , na wartość niezmiennej w rozłącznego związek G i H jest sumą wartości na G i w H . Na przykład, liczba wierzchołków jest dodatek.
  • Wykres jest niezmienny mnożnikowy , jeżeli dla wszystkich dwóch wykresów G i H , wartość niezmiennej w rozłącznego związek G i H jest iloczynem wartości na G i w H . Na przykład, wskaźnik Hosoya (ilość skojarzeń) jest mnożnikowy.
  • Wykres niezmienna jest maxing , jeżeli dla wszystkich dwóch wykresów G i H , wartość niezmiennej w rozłącznego związek G i H są maksymalne wartości na G i w H . Na przykład, liczba chromatyczna jest maxing.

Ponadto, właściwości wykres można klasyfikować według typu wykresu są określenia: czy wykres jest nieukierunkowane lub skierowane zarówno właściwość dotyczy multigraphs , etc.

Wartości niezmienników

Docelowy zestaw funkcji, która wyznacza niezmiennik wykresu mogą być:

Niezmienniki wykres i wykres Izomorfizm

Łatwo obliczalne są niezmienniki wykres instrumentalny do szybkiego rozpoznawania izomorfizm grafów , czy raczej braku izomorfizmu, ponieważ dla każdego niezmienna w ogóle, dwa wykresy z różnymi wartościami nie może (z definicji) są izomorficzne. Dwa wykresy z tymi samymi niezmienników może lub nie może być izomorficzne, jednak.

Wykres niezmienna I ( G ) jest zwana pełna czy tożsamość invarianty I ( G ) i I ( H ) oznacza izomorfizmu wykresy, G i H . Znalezienie efektywnie-obliczalny taki niezmiennik (problem wykresu kanonizacji ) oznaczałoby proste rozwiązanie trudnego problemu izomorfizm grafów . Jednak nawet wielomianowe Niezmienniki wartościach takich jak chromatycznej wielomian zazwyczaj nie są kompletne. Wykres pazur i wykres ścieżka 4 wierzchołków mają taki sam wielomian chromatyczną, na przykład.

Przykłady

Nieruchomości

Integer niezmienniki

liczba rzeczywista niezmienniki

Ciągi i wielomiany

Zobacz też

Referencje