Operazioni sui grafici - Graph operations
Le operazioni sui grafici producono nuovi grafici da quelli iniziali. Possono essere suddivisi nelle seguenti categorie principali.
Operazioni unarie
Le operazioni unarie creano un nuovo grafico da un singolo grafico iniziale.
Operazioni elementari
Operazioni elementari o operazioni di modifica, note anche come operazioni di modifica del grafico, creare un nuovo grafico da quello iniziale con una semplice modifica locale, come l'aggiunta o la cancellazione di un vertice o di un bordo, fusione e divisione dei vertici, contrazione del bordo , ecc. Il grafico modifica la distanza tra una coppia di grafi è il numero minimo di operazioni elementari richieste per trasformare un grafo nell'altro.
Operazioni avanzate
Le operazioni avanzate creano un nuovo grafico da quello iniziale mediante modifiche complesse, come ad esempio:
- trasporre grafico ;
- complemento grafico ;
- grafico a linee ;
- grafico minore ;
- riscrittura di grafici ;
- potenza del grafico ;
- doppio grafico ;
- grafico mediale ;
- grafico quoziente ;
- Trasformata Y-Δ ;
- Mycielskian .
Operazioni binarie
Le operazioni binarie creano un nuovo grafico da due grafici iniziali G 1 = ( V 1 , E 1 ) e G 2 = ( V 2 , E 2 ) , come ad esempio:
- unione del grafico: G 1 ∪ G 2 . Esistono due definizioni. Nella più comune, l' unione disgiunta di grafi , si presume che l'unione sia disgiunta. Meno comunemente (sebbene più coerente con la definizione generale di unione in matematica) l'unione di due grafi è definita grafo ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- intersezione del grafico: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ;
- grafo join: grafo con tutti i bordi che collegano i vertici del primo grafo con i vertici del secondo grafo. È un'operazione commutativa (per grafici senza etichetta);
-
prodotti grafici basati sul prodotto cartesiano degli insiemi di vertici:
- prodotto grafico cartesiano : è un'operazione commutativa e associativa (per grafi non etichettati),
- prodotto grafico lessicografico (o composizione grafico): è un'operazione associativa (per grafici senza etichetta) e non commutativa,
- prodotto grafico forte : è un'operazione commutativa e associativa (per grafi senza etichetta),
- prodotto grafico tensoriale (o prodotto grafico diretto, prodotto grafico categoriale, prodotto grafico cardinale, prodotto grafico Kronecker): è un'operazione commutativa e associativa (per grafici senza etichetta),
- prodotto grafico a zig-zag ;
- prodotto grafico basato su altri prodotti:
- prodotto grafo radicato : è un'operazione associativa (per grafi non etichettati ma radicati),
- prodotto grafico corona : è un'operazione non commutativa;
-
composizione grafo serie-parallelo :
- composizione di grafi paralleli: è un'operazione commutativa (per grafi senza etichetta),
- composizione del grafico in serie: è un'operazione non commutativa,
- composizione grafo sorgente: è un'operazione commutativa (per grafi senza etichetta);
- Hajós costruzione .
Appunti
- ^ Bondy, JA; Murty, USR (2008). Teoria dei grafi . Testi laureati in matematica. Springer. p. 29. ISBN 978-1-84628-969-9 .
- ^ A b c Harary, F . Teoria dei grafi . Reading, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). "Onde di entropia, il prodotto grafico a zig-zag e nuovi espansori a grado costante". Annali di matematica . 155 (1): 157–187. arXiv : math / 0406038 . doi : 10.2307 / 3062153 . JSTOR 3062153 . MR 1.888.797 .
- ^ Frucht, Robert ; Harary, Frank (1970). "Sulla corona di due grafici". Aequationes Mathematicae . 4 : 322–324. doi : 10.1007 / bf01844162 . hdl : 2027.42 / 44326 .
