Operace s grafy

Operace s grafy tvoří nové grafy ze starých. Operace lze rozdělit do následujících hlavních kategorií.

Jednoduché (unární) operace

Jediná operace vytvoří nový graf ze starého.

Elementární operace

Někdy se tato třída operací nazývá operace úpravy grafů. Vytvářejí nový graf z původního grafu jednoduchými lokálními změnami, jako je přidání nebo odebrání vrcholu nebo oblouku, sloučení nebo rozdělení vrcholů, zmenšení grafu a tak dále.

Složité operace

Složené operace vytvoří nový graf z původního se složitými změnami, jako jsou:

• hranový graf
• Duální graf
• Doplněk grafu
• Hrabě menší
• Stupeň grafu : K -tý stupeň G k grafu G je supergraf vytvořený sečtením všech oblouků mezi všechny dvojice vrcholů G se vzdáleností nejvýše k . Druhá mocnina grafu se také nazývá jeho druhá mocnina .
• Převod Delta-Star
• hrabě Mychelski (Mychelskian)

Dvojité (binární) operace

Binární operace vytvoří nový graf ze dvou původních grafů G1(V1, E1) a G2(V2, E2) :

• Disjunktní sjednocení grafů nebo jednoduše sjednocení grafů  je graf obsahující sjednocení (disjunktních) vrcholových množin V1 a V2 grafů a obloukových množin, tedy [1] . Operace je komutativní a asociativní (pro neoznačené grafy ).
• Spojení dvou grafů je spojením dvou grafů, ve kterém se sečtou všechny oblouky spojující vrcholy obou grafů (tedy oblouky, jejichž vrcholy jsou převzaty z různých grafů) [1] . Operace je komutativní (pro neoznačené grafy).
• Součin grafů založených na přímém součinu množin vrcholů:
  • Přímým součinem grafů [1] je komutativní a asociativní operace (u neoznačených grafů).
  • Lexikografický součin grafů [1] . Operace není komutativní ani asociativní.
  • Silný produkt grafů .
  • Tenzorový součin grafů , někdy také nazývaný přímý součin nebo Kroneckerův součin . Operace je komutativní (pro neoznačené grafy).
  • Cikcak součin [2] .

Označme [N] množinu celých čísel od 1 do N. K určení klikatého součinu se používají k- pravidelné grafy , jejichž oblouky jsou vybarveny k barvami. Pro každou barvu i a vrchol v označme v [ i ] souseda vrcholu v spojeného obloukem barvy i . Nechť G1 je D1-regulární graf nad [N1] a G2 je D2-regulární graf nad [D1]. Pak klikatým součinem H je graf s množinou vrcholů [N1] × [D1], ve kterém pro libovolné n z [N1], d z [D1] ai, j z [D2] je vrchol (n , d) je připojen k ( n [ d [ i ]], d [ i ][ j ]). Tato definice se používá pro vytváření expandérů .

• Další operace s grafy s názvem "produkt":
  • Kořenový součin grafů . Operace není komutativní ani asociativní.
  • Koronální součin grafů G1 a G2 (definovaný Fruchtem a Hararim [3] ) je graf, který je sjednocením jedné kopie grafu G1 a |V1| kopie grafu G2 (|V1| je počet vrcholů grafu G1), ve kterém je každý vrchol kopie G1 spojen se všemi vrcholy všech kopií G2.
• Tvorba paralelně-sekvenčních grafů :
  • paralelní složení. Operace je komutativní (pro neoznačené grafy) [4] .
  • sekvenční složení. Operace je nekomutativní [4] .
  • Složení pramenů (fúze pramenů). Komutativní operace (pro neoznačené grafy).
• hrabě Hajosh .

Poznámky

1. ↑ 1 2 3 4 F. Harari . Graph Theory = Graph Theory / Překlad z angličtiny a předmluva V.P. Kozyreva. - 2. - M. : Editorial URSS, 2003. - 296 s.
2. ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Vlny entropie, součin klikatých grafů a nové expandéry konstantních stupňů  // Annals of Mathematics . - 2002. - T. 155 , no. 1 . - S. 157-187 . - doi : 10.2307/3062153 . — .
3. ↑ Robert Frucht a Frank Harary . „O korónách dvou grafů“, Aequationes Math. 4:322-324,1970.
4. ↑ 1 2 Evstigneev V. A., Kasyanov V. N. Sériově paralelní poset // Slovník grafů v informatice / Edited by prof. Viktor Nikolajevič Kasjanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Návrh a optimalizace programů). - ISBN 978-591124-036-3 .