Grafické operace - Graph operations
Grafické operace vyrábět nové grafy od počátečních. Lze je rozdělit do následujících hlavních kategorií.
Unární operace
Unární operace vytvoří nový graf z jediného počátečního grafu.
Základní operace
Základní operace nebo editační operace, které jsou také známé jako operace úprav grafů, vytvoření nového grafu z jednoho počátečního jednoduchou místní změnou, jako je přidání nebo odstranění vrcholu nebo hrany, sloučení a rozdělení vrcholů, kontrakce hran atd vzdálenost pro úpravy grafů mezi dvojicí grafů je minimální počet elementárních operací potřebných k transformaci jednoho grafu do druhého.
Pokročilé operace
Pokročilé operace vytvářejí nový graf od počátečního pomocí komplexních změn, například:
- transponovat graf;
- doplňkový graf;
- hranový graf;
- graf minor;
- přepis grafu;
- síla grafu;
- duální graf;
- mediální graf;
- kvocient kvocientu;
- Transformace Y-Δ;
- Mycielskian.
Binární operace
Binární operace vytvoří nový graf ze dvou počátečních grafů G1 = (PROTI1, E1) a G2 = (PROTI2, E2), jako:
- unie grafů: G1 ∪ G2. Existují dvě definice. V nejběžnější je disjunktní spojení grafů, unie se předpokládá disjunktní. Méně často (i když více v souladu s obecnou definicí unie v matematice) je spojení dvou grafů definováno jako graf (PROTI1 ∪ PROTI2, E1 ∪ E2).
- křižovatka grafu: G1 ∩ G2 = (PROTI1 ∩ PROTI2, E1 ∩ E2);[1]
- spojení grafu: graf se všemi hranami, které spojují vrcholy prvního grafu s vrcholy druhého grafu. Je to komutativní operace (pro neoznačené grafy);[2]
- grafové produkty založeno na kartézský součin množin vrcholů:
- kartézský graf: je to komutativní a asociativní operace (pro neznačené grafy),[2]
- lexikografický grafový produkt (nebo složení grafu): jedná se o asociativní (u neznačených grafů) a nekomutativní operaci,[2]
- silný grafový produkt: je to komutativní a asociativní operace (pro neznačené grafy),
- produkt tenzorového grafu (nebo produkt přímého grafu, produkt kategorického grafu, produkt kardinálního grafu, produkt grafu Kronecker): jedná se o komutativní a asociativní operaci (pro neoznačené grafy),
- klikatý grafový produkt;[3]
- graf produktu na základě jiných produktů:
- zakořeněný grafový produkt: je to asociativní operace (pro neoznačené, ale zakořeněné grafy),
- produkt koronového grafu: je to nekomutativní operace;[4]
- sériově paralelní složení grafu:
- paralelní složení grafu: je to komutativní operace (pro neznačené grafy),
- složení grafu řady: jedná se o nekomutativní operaci,
- složení zdrojového grafu: jedná se o komutativní operaci (u neznačených grafů);
- Hajósova konstrukce.
Poznámky
- ^ Bondy, J. A .; Murty, USA (2008). Teorie grafů. Postgraduální texty z matematiky. Springer. p. 29. ISBN 978-1-84628-969-9.
- ^ A b C Harary, F. Teorie grafů. Reading, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). „Entropické vlny, produkt klikatého grafu a nové expandéry konstantního stupně“. Annals of Mathematics. 155 (1): 157–187. arXiv:matematika / 0406038. doi:10.2307/3062153. JSTOR 3062153. PAN 1888797.
- ^ Frucht, Robert; Harary, Franku (1970). "Na koroně dvou grafů". Aequationes Mathematicae. 4: 322–324. doi:10.1007 / bf01844162. hdl:2027.42/44326.