En la teoría de grafos , una rama de las matemáticas, la unión disjunta de gráficos es una operación que combina dos o más gráficos para formar un gráfico 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 gráficos dados, y haciendo que el conjunto de aristas del resultado sea la unión disjunta de la arista. conjuntos de los gráficos dados. Cualquier unión disjunta de dos o más gráficos no vacíos está necesariamente desconectada .
Notación
La unión disjunta también se denomina suma gráfica y se puede representar mediante un signo más o un signo más encerrado en un círculo: Si y son dos gráficos, entonces o denota su unión disjunta. [1]
Clases de grafos relacionados
Ciertas clases especiales de gráficos se pueden representar mediante operaciones de unión disjuntas. En particular:
- Los bosques son las uniones inconexas de árboles . [2]
- Los gráficos de conglomerados son las uniones disjuntas de gráficos completos . [3]
- Las gráficas 2-regulares son las uniones disjuntas de las gráficas cíclicas . [4]
De manera más general, cada gráfico es la unión disjunta de gráficos conectados , sus componentes conectados .
Las cografías son las gráficas que se pueden construir a partir de gráficas de un solo vértice mediante una combinación de operaciones de unión y complemento disjuntas . [5]
Referencias
- ^ Rosen, Kenneth H. (1999), Manual de matemáticas discretas y combinatorias , Matemáticas discretas y sus aplicaciones, CRC Press, p. 515, ISBN 9780849301490
- ^ Grossman, Jerrold W. (1990), Matemáticas discretas: Introducción a conceptos, métodos y aplicaciones , Macmillan, p. 627, ISBN 9780023483318
- ^ Gráficos de clúster , sistema de información sobre clases de gráficos y sus inclusiones, consultado el 26 de junio de 2016.
- ^ Chartrand, Gary; Zhang, Ping (2013), Un primer curso de teoría de grafos , Dover Books on Mathematics, Courier Corporation, p. 201, ISBN 9780486297309
- ^ Corneil, DG ; Lerchs, H .; Stewart Burlingham, L. (1981), "Gráficos reducibles de complemento", Matemáticas aplicadas discretas , 3 (3): 163-174, doi : 10.1016 / 0166-218X (81) 90013-5 , MR 0619603