Operationer på grafer

Operationer på grafer danner nye grafer fra gamle. Operationer kan opdeles i følgende hovedkategorier.

Enkelte (unære) operationer

En enkelt handling skaber en ny graf fra en gammel.

Elementære operationer

Nogle gange kaldes denne klasse af operationer grafredigeringsoperationer. De opretter en ny graf ud fra den originale graf ved simple, lokale ændringer, såsom tilføjelse eller fjernelse af et toppunkt eller en bue, fletning eller opdeling af hjørner, formindskelse af grafen og så videre.

Komplekse operationer

Sammensatte operationer skaber en ny graf fra den oprindelige med komplekse ændringer, såsom:

• linje graf
• Dobbelt graf
• Grafkomplement
• Tæl mindre
• Grafens grad : Den k'te grad G k af grafen G er en supergraf dannet ved at addere alle buer mellem alle par af toppunkter af G med afstand højst k . Anden potens af en graf kaldes også dens kvadrat .
• Delta-Star konvertering
• Grev Mychelski (Mychelskian)

Dobbelt (binære) operationer

Den binære operation opretter en ny graf fra de to originale grafer G1(V1, E1) og G2(V2, E2) :

• En usammenhængende grafforening, eller blot en grafforening,  er en graf, der indeholder foreningen af ​​(usammenhængende) toppunkter V1 og V2 af grafer og buesæt, dvs. [1] . Operationen er kommutativ og associativ (for umærkede grafer ).
• Forbindelsen af ​​to grafer er foreningen af ​​to grafer, hvor alle de buer, der forbinder toppunkterne på begge grafer, tilføjes (det vil sige buerne, hvis toppunkter er taget fra forskellige grafer) [1] . Operationen er kommutativ (for umærkede grafer).
• Produktet af grafer baseret på det direkte produkt af sæt af hjørner:
  • Det direkte produkt af grafer [1] er en kommutativ og associativ operation (for umærkede grafer).
  • Leksikografisk produkt af grafer [1] . Operationen er hverken kommutativ eller associativ.
  • Stærkt produkt af grafer .
  • Tensorprodukt af grafer , nogle gange også kaldet direkte produkt eller Kronecker produkt . Operationen er kommutativ (for umærkede grafer).
  • Zigzag produkt [2] .

Lad [N] betegne mængden af ​​heltal fra 1 til N. For at bestemme zigzag-produktet bruges k- regulære grafer , hvis buer er farvet i k farver. For hver farve i og toppunkt v , lad v [ i ] betegne naboen til toppunkt v forbundet med en bue med farve i . Lad G1 være en D1-regulær graf over [N1] og G2 være en D2-regulær graf over [D1]. Så er zigzag-produktet af H grafen med toppunktet [N1] × [D1], hvori for enhver n fra [N1], d fra [D1] og i, j fra [D2], toppunktet (n) , d) er forbundet med ( n [ d [ i ]], d [ i ][ j ]). Denne definition bruges til at bygge expandere .

• Andre handlinger på grafer med navnet "produkt":
  • Rodprodukt af grafer . Operationen er hverken kommutativ eller associativ.
  • Koronalproduktet af graferne G1 og G2 (defineret af Frucht og Harari [3] ) er en graf, der er foreningen af ​​én kopi af grafen G1 og |V1| kopier af grafen G2 (|V1| er antallet af hjørner af grafen G1), hvor hvert hjørne af kopien af ​​G1 er forbundet med alle hjørner af alle kopier af G2.
• Oprettelse af parallel-sekventielle grafer :
  • parallel komposition. Operationen er kommutativ (for umærkede grafer) [4] .
  • sekventiel sammensætning. Operationen er ikke-kommutativ [4] .
  • Sammensætning af kilder (fusion af kilder). Kommutativ operation (for umærkede grafer).
• Grev Hajosh .

Noter

1. ↑ 1 2 3 4 F. Harari . Graph Theory = Graph Theory / Oversættelse fra engelsk og forord af V.P. Kozyrev. - 2. - M. : Redaktionel URSS, 2003. - 296 s.
2. ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Entropibølger, zig-zag-grafproduktet og nye konstant-graders ekspandere  // Annals of Mathematics . - 2002. - T. 155 , no. 1 . - S. 157-187 . - doi : 10.2307/3062153 . — .
3. ↑ Robert Frucht og Frank Harary . "På koronas af to grafer", Aequationes Math. 4:322-324, 1970.
4. ↑ 1 2 Evstigneev V. A., Kasyanov V. N. Serie-parallel poset // Dictionary of graphs in computer science / Redigeret af prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Design og optimering af programmer). - ISBN 978-591124-036-3 .