Unión disjunta de grafos

En teoría de grafos , una rama de las matemáticas, la unión disjunta de grafos es una operación que combina dos o más grafos para formar un grafo más grande. Es análoga a la unión disjunta de conjuntos y se construye haciendo que el conjunto de vértices del resultado sea la unión disjunta de los conjuntos de vértices de los grafos dados, y haciendo que el conjunto de aristas del resultado sea la unión disjunta de los conjuntos de aristas de los grafos dados. Cualquier unión disjunta de dos o más grafos no vacíos es necesariamente desconectada .

La unión disjunta también se denomina suma de grafos y puede representarse mediante un signo más o un signo más dentro de un círculo: Si y son dos grafos, entonces o denota su unión disjunta. ^[1]${\estilo de visualización G}$${\estilo de visualización H}$${\estilo de visualización G+H}$${\displaystyle G\oplus H}$

Ciertas clases especiales de grafos pueden representarse mediante operaciones de unión disjunta. En particular:

• Los bosques son las uniones disjuntas de árboles . ^[2]
• Los grafos de conglomerados son las uniones disjuntas de grafos completos . ^[3]
• Los grafos 2-regulares son las uniones disjuntas de los grafos cíclicos . ^[4]

De manera más general, cada gráfico es la unión disjunta de gráficos conexos , sus componentes conexos .

Los cografos son los gráficos que pueden construirse a partir de gráficos de un solo vértice mediante una combinación de operaciones de unión disjunta y complemento . ^[5]