Operacje na wykresach

W matematycznej dziedzinie teorii grafów operacje na grafach to operacje , które tworzą nowe grafy na podstawie grafów początkowych. Obejmują one zarówno jednoargumentowe (jedno wejście), jak i binarne (dwa wejścia).

Operacje jednoargumentowe

Operacje jednoargumentowe tworzą nowy graf z pojedynczego grafu początkowego.

Operacje elementarne

Operacje elementarne lub operacje edycyjne, znane również jako operacje edycji grafu, tworzą nowy graf z jednego początkowego poprzez prostą zmianę lokalną, taką jak dodanie lub usunięcie wierzchołka lub krawędzi, łączenie i dzielenie wierzchołków, skracanie krawędzi , itp. Odległość edycji wykresu między parą wykresów to minimalna liczba elementarnych operacji wymaganych do przekształcenia jednego wykresu w drugi.

Zaawansowane operacje

Zaawansowane operacje tworzą nowy wykres z początkowego poprzez złożone zmiany, takie jak:

Operacje binarne

Operacje binarne tworzą nowy graf z dwóch grafów początkowych G ₁ = ( V ₁ , E ₁ ) i G ₂ = ( V ₂ , E ₂ ) , na przykład:

suma wykresów: G ₁ ∪ G ₂ . Istnieją dwie definicje. W najbardziej powszechnym, rozłącznym związku grafów , zakłada się, że związek jest rozłączny. Rzadziej (choć bardziej zgodnie z ogólną definicją sumy w matematyce) suma dwóch grafów jest definiowana jako graf ( V ₁ ∪ V ₂ , E ₁ ∪ E ₂ ) .
przecięcie wykresu: G ₁ ∩ G ₂ = ( V ₁ ∩ V ₂ , mi ₁ ∩ mi ₂ ) ;
graph join: graf ze wszystkimi krawędziami łączącymi wierzchołki pierwszego grafu z wierzchołkami drugiego grafu. Jest to operacja przemienna (dla grafów bez etykiet);
produkty grafów oparte na iloczynie kartezjańskim zbiorów wierzchołków:
- iloczyn grafów kartezjańskich : jest to operacja przemienna i asocjacyjna (dla grafów nieoznaczonych),
- iloczyn grafu leksykograficznego (lub skład grafu): jest to operacja asocjacyjna (dla grafów nieetykietowanych) i nieprzemienna,
- silny produkt grafowy : jest to operacja przemienna i asocjacyjna (dla grafów nieoznaczonych),
- iloczyn grafu tensorowego (lub iloczyn grafu bezpośredniego, iloczyn grafu kategorialnego, iloczyn grafu kardynalnego, produkt grafu Kroneckera): jest to operacja przemienna i asocjacyjna (dla grafów nieetykietowanych),
- iloczyn grafu zygzakowatego ;
wykres produktu na podstawie innych produktów:
- ukorzeniony iloczyn grafów : jest to operacja asocjacyjna (dla nieoznakowanych, ale ukorzenionych grafów),
- produkt wykresu koronowego: jest to operacja nieprzemienna;
skład wykresu szeregowo-równoległego :
- równoległa kompozycja grafu: jest to operacja przemienna (dla grafów nieoznaczonych),
- skład grafu szeregowego: jest to operacja nieprzemienna,
- skład grafu źródłowego: jest to operacja przemienna (dla grafów nieoznakowanych);
Konstrukcja Hajós .

Notatki

Bibliografia _ Murty, USR (2008). Teoria grafów . Absolwent Teksty z matematyki. Skoczek. P. 29. ISBN 978-1-84628-969-9 .
^_ ^ ^abc ^Harary , F. Teoria grafów . Czytanie, MA: Addison-Wesley, 1994.
Bibliografia _ Vadhan, S.; Wigderson, A. (2002). „Fale entropii, iloczyn wykresu zygzakowatego i nowe ekspandery o stałym stopniu”. Roczniki matematyki . 155 (1): 157–187. arXiv : matematyka/0406038 . doi : 10.2307/3062153 . JSTOR 3062153 . MR 1888797 .
Bibliografia _ _ Harary, Frank (1970). „Na koronie dwóch wykresów”. Aequationes Mathematicae . 4 : 322–324. doi : 10.1007/bf01844162 . hdl : 2027.42/44326 .

[bondy_murty-1] Bibliografia _ Murty, USR (2008). Teoria grafów . Absolwent Teksty z matematyki. Skoczek. P. 29. ISBN 978-1-84628-969-9 .

[harary-2] _ ^ ^abc ^Harary , F. Teoria grafów . Czytanie, MA: Addison-Wesley, 1994.

[3] Bibliografia _ Vadhan, S.; Wigderson, A. (2002). „Fale entropii, iloczyn wykresu zygzakowatego i nowe ekspandery o stałym stopniu”. Roczniki matematyki . 155 (1): 157–187. arXiv : matematyka/0406038 . doi : 10.2307/3062153 . JSTOR 3062153 . MR 1888797 .

[4] Bibliografia _ _ Harary, Frank (1970). „Na koronie dwóch wykresów”. Aequationes Mathematicae . 4 : 322–324. doi : 10.1007/bf01844162 . hdl : 2027.42/44326 .