Grafhandlingar - Graph operations
Diagramåtgärder ger nya grafer från initiala. De kan delas in i följande huvudkategorier.
Unary verksamhet
Unary-operationer skapar ett nytt diagram från en enda initial graf.
Elementära operationer
Elementära operationer eller redigeringsåtgärder, som också kallas grafredigeringsåtgärder, skapa ett nytt diagram från en initial med en enkel lokal förändring, såsom tillägg eller radering av ett toppunkt eller en kant, sammanslagning och delning av vertikaler, kantkontraktion etc. Diagrammet redigerar avståndet mellan ett par grafer är det minsta antal elementära operationer som krävs för att omvandla en graf till den andra.
Avancerade operationer
Avancerade operationer skapar en ny graf från början med komplexa förändringar, till exempel:
- transponera diagram ;
- komplettera diagram ;
- linjediagram ;
- diagram mindre ;
- omskrivning av diagram ;
- kraften i diagrammet ;
- dubbel graf ;
- medial graf ;
- kvotdiagram ;
- Y-A-transform ;
- Mycielskian .
Binär verksamhet
Binära operationer skapar en ny graf från två initiala diagram G 1 = ( V 1 , E 1 ) och G 2 = ( V 2 , E 2 ) , såsom:
- grafförening: G 1 ∪ G 2 . Det finns två definitioner. I det vanligaste, den disjunkta unionen av grafer är förbundet antas vara disjunkta. Mindre vanligt (men mer överensstämmande med den allmänna definitionen av union i matematik) definieras föreningen av två grafer som diagrammet ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- grafkorsning: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ;
- graph join: diagram med alla kanter som förbinder topparna i den första grafen med topparna i den andra grafen. Det är en kommutativ operation (för omärkta grafer);
-
grafiska produkter baserade på den kartesiska produkten från vertexuppsättningarna:
- kartesisk grafprodukt : det är en kommutativ och associerande operation (för omärkta grafer),
- lexikografisk grafprodukt (eller grafkomposition): den är en associerande (för omärkta grafer) och icke-kommutativ operation,
- stark grafprodukt : det är en kommutativ och associerande operation (för omärkta grafer),
- tensorgrafprodukt (eller direktgrafprodukt, kategorisk grafprodukt, kardinalprodukt, Kronecker-grafprodukt): det är en kommutativ och associerande operation (för omärkta grafer),
- sicksack-grafprodukt ;
- graf produkt baserad på andra produkter:
- rotad grafprodukt : det är en associerande operation (för omärkta men rotade grafer),
- corona-grafprodukt : det är en icke-kommutativ operation;
-
serie – parallell grafkomposition :
- parallell grafkomposition: det är en kommutativ operation (för omärkta grafer),
- seriens grafkomposition: det är en icke-kommutativ operation,
- källgrafsammansättning: det är en kommutativ operation (för omärkta grafer);
- Hajós konstruktion .
Anteckningar
- ^ Bondy, JA; Murty, USR (2008). Grafteori . Graduate Texts in Mathematics. Springer. sid. 29. ISBN 978-1-84628-969-9 .
- ^ A b c Harary, F . Grafteori . Reading, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). "Entropivågor, sicksackdiagramprodukten och nya utvidgare med konstant grad". Matematikens annaler . 155 (1): 157–187. arXiv : matematik / 0406038 . doi : 10.2307 / 3062153 . JSTOR 3062153 . MR 1888797 .
- ^ Frucht, Robert ; Harary, Frank (1970). "På korona med två grafer". Aequationes Mathematicae . 4 : 322–324. doi : 10.1007 / bf01844162 . hdl : 2027.42 / 44326 .