Operationer på grafer
Operationer på grafer bildar nya grafer från gamla. Verksamheten kan delas in i följande huvudkategorier.
Enstaka (unära) operationer
En enda operation skapar en ny graf från en gammal.
Elementära operationer
Ibland kallas denna klass av operationer för grafredigeringsoperationer. De skapar en ny graf från den ursprungliga grafen genom enkla, lokala ändringar, som att lägga till eller ta bort en vertex eller båge, slå samman eller dela hörn, krympa grafen och så vidare.
Komplexa operationer
Sammansatta operationer skapar en ny graf från den ursprungliga med komplexa ändringar, som:
- linjediagram
- Dubbel graf
- Grafkomplement
- Räkna mindre
- Grafens grad : Den k: te graden G k i grafen G är en supergraf som bildas genom att addera alla bågar mellan alla par av hörn av G med avstånd som högst k . Andra potensen av en graf kallas också dess kvadrat .
- Delta-Star-konvertering
- Greve Mychelski (Mychelskian)
Dubbla (binära) operationer
Den binära operationen skapar en ny graf från de två ursprungliga graferna G1(V1, E1) och G2(V2, E2) :
- En disjunkt grafunion, eller helt enkelt en grafunion, är en graf som innehåller föreningen av (disjunkta) vertexuppsättningar V1 och V2 av grafer och båguppsättningar, d.v.s. [1] . Operationen är kommutativ och associativ (för omärkta grafer ).
- Kopplingen av två grafer är föreningen av två grafer, där alla bågar som förbinder de båda grafernas hörn adderas (det vill säga bågarna, vars hörn är hämtade från olika grafer) [1] . Operationen är kommutativ (för omärkta grafer).
- Produkten av grafer baserade på den direkta produkten av uppsättningar av hörn:
- Den direkta produkten av grafer [1] är en kommutativ och associativ operation (för omärkta grafer).
- Lexikografisk produkt av grafer [1] . Operationen är varken kommutativ eller associativ.
- Stark produkt av grafer .
- Tensorprodukt av grafer , ibland även kallad direktprodukt eller Kroneckerprodukt . Operationen är kommutativ (för omärkta grafer).
- Sicksackprodukt [2] .
Låt [N] beteckna mängden heltal från 1 till N. För att bestämma sicksackprodukten används k- reguljära grafer , vars bågar är färgade i k färger. För varje färg i och vertex v , låt v [ i ] beteckna granne till vertex v förenad med en båge av färg i . Låt G1 vara en D1-regelbunden graf över [N1] och G2 vara en D2-regelbunden graf över [D1]. Sedan är sicksackprodukten av H grafen med vertexuppsättningen [N1] × [D1], där för vilket n som helst från [N1], d från [D1] och i, j från [D2], vertexet (n , d) är ansluten till ( n [ d [ i ]], d [ i ][ j ]). Denna definition används för att bygga expanders .
- Andra operationer på grafer som heter "produkt":
- Rotprodukt av grafer . Operationen är varken kommutativ eller associativ.
- Den koronala produkten av graferna G1 och G2 (definierad av Frucht och Harari [3] ) är en graf som är föreningen av en kopia av grafen G1 och |V1| kopior av grafen G2 (|V1| är antalet hörn av grafen G1), där varje hörn av kopian av G1 är kopplad till alla hörn av alla kopior av G2.
- Skapa parallell-sekventiella grafer :
- Greve Hajosh .
Anteckningar
- ↑ 1 2 3 4 F. Harari . Graph Theory = Graph Theory / Översättning från engelska och förord av V.P. Kozyrev. - 2. - M. : Redaktionell URSS, 2003. - 296 sid.
- ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Entropivågor, sicksack-grafprodukten och nya konstantgradiga expanderare // Annals of Mathematics . - 2002. - T. 155 , nr. 1 . - S. 157-187 . - doi : 10.2307/3062153 . — .
- ↑ Robert Frucht och Frank Harary . "På koronas av två grafer", Aequationes Math. 4:322-324, 1970.
- ↑ 1 2 Evstigneev V. A., Kasyanov V. N. Serieparallell poset // Dictionary of graphs in data science / Redigerad av prof. Viktor Nikolaevich Kasyanov. - Novosibirsk: LLC "Siberian Scientific Publishing House", 2009. - V. 17. - (Design och optimering av program). - ISBN 978-591124-036-3 .