Operações de gráfico - Graph operations
As operações de gráfico produzem novos gráficos a partir dos iniciais. Eles podem ser separados nas seguintes categorias principais.
Operações unárias
As operações unárias criam um novo gráfico a partir de um único gráfico inicial.
Operações elementares
Operações elementares ou operações de edição, também conhecidas como operações de edição de gráfico, crie um novo gráfico a partir de um inicial por uma simples mudança local, como adição ou exclusão de um vértice ou de uma aresta, fusão e divisão de vértices, contração de aresta , etc. O gráfico edita a distância entre um par de graphs é o número mínimo de operações elementares necessárias para transformar um gráfico no outro.
Operações avançadas
As operações avançadas criam um novo gráfico a partir do inicial por meio de alterações complexas, como:
- transpor gráfico ;
- gráfico de complemento ;
- gráfico de linha ;
- gráfico menor ;
- reescrita de gráfico ;
- poder do gráfico ;
- gráfico duplo ;
- gráfico medial ;
- gráfico de quociente ;
- Transformada Y-Δ ;
- Mycielskian .
Operações binárias
As operações binárias criam um novo gráfico a partir de dois gráficos iniciais G 1 = ( V 1 , E 1 ) e G 2 = ( V 2 , E 2 ) , como:
- união do gráfico: G 1 ∪ G 2 . Existem duas definições. No mais comum, a união disjunta de gráficos , a união é considerada disjunta. Menos comumente (embora mais consistente com a definição geral de união em matemática), a união de dois gráficos é definida como o gráfico ( V 1 ∪ V 2 , E 1 ∪ E 2 ) .
- intersecção do gráfico: G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) ;
- graph join: gráfico com todas as arestas que conectam os vértices do primeiro gráfico com os vértices do segundo gráfico. É uma operação comutativa (para gráficos não rotulados);
-
produtos gráficos com base no produto cartesiano dos conjuntos de vértices:
- produto gráfico cartesiano : é uma operação comutativa e associativa (para gráficos não rotulados),
- Produto gráfico lexicográfico (ou composição gráfica): é uma operação associativa (para gráficos não marcados) e não comutativa,
- produto gráfico forte : é uma operação comutativa e associativa (para gráficos não marcados),
- produto gráfico tensorial (ou produto gráfico direto, produto gráfico categórico, produto gráfico cardinal, produto gráfico Kronecker): é uma operação comutativa e associativa (para gráficos não marcados),
- produto gráfico zig-zag ;
- produto gráfico com base em outros produtos:
- produto gráfico enraizado : é uma operação associativa (para gráficos não rotulados, mas enraizados),
- produto gráfico corona : é uma operação não comutativa;
-
composição do gráfico série-paralelo :
- composição de grafos paralelos: é uma operação comutativa (para grafos não marcados),
- composição do gráfico de série: é uma operação não comutativa,
- composição do gráfico de origem: é uma operação comutativa (para gráficos não rotulados);
- Construção Hajós .
Notas
- ^ Bondy, JA; Murty, USR (2008). Teoria dos grafos . Textos de Pós-Graduação em Matemática. Springer. p. 29. ISBN 978-1-84628-969-9 .
- ^ Uma b c Harary, F . Teoria dos grafos . Reading, MA: Addison-Wesley, 1994.
- ^ Reingold, O .; Vadhan, S .; Wigderson, A. (2002). "Ondas de entropia, o produto gráfico em zigue-zague e novos expansores de grau constante". Annals of Mathematics . 155 (1): 157–187. arXiv : math / 0406038 . doi : 10.2307 / 3062153 . JSTOR 3062153 . MR 1888797 .
- ^ Frucht, Robert ; Harary, Frank (1970). "Na coroa de dois gráficos". Aequationes Mathematicae . 4 : 322–324. doi : 10.1007 / bf01844162 . hdl : 2027,42 / 44326 .
