Teorema de Brooks

Teorema de Brooks

En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático:

Si G es un grafo conexo que no sea completo ni un ciclo de longitud impar, entonces \chi (G)\le \Delta \,


R. L. Brooks, (1941)

En donde Δ es la valencia máxima del grafo G.

Demostración básica

La siguiente demostración es sólo para grafos no regulares. Basta buscar una ordenación adecuada y aplicar el algoritmo voraz para colorear secuencialmente.

Sea G un grafo de n vértices y x un vértice tal que g(x)=s < \Delta \, (que existe por la no regularidad). El vértice x lo colocamos en el último lugar de la ordenación, es decir, x=vn . Los vértices adyacentes a x los enumeramos vn-s, vn-s-1, ..., vn-1, luego consideramos los adyacentes a vn-1 que no han sido ordenados, luego los de vn-2, y así hasta ordenarlos todos (lo cual es posible al ser G conexo).

En esta ordenación {v1, v2, ..., vn}, todos los vértices tienen un vértice (o más) adyacente posterior (con subíndice mayor) excepto el vértice x . Luego, el número de vértices adyacentes con subíndice menor es igual o menor a Δ .

Al aplicar el algoritmo voraz para colorear surgen los colores prohibidos. El número de colores prohibidos en el paso k de la ejecución del algoritmo es el número de colores usados por lo vértices adyacentes anteriores, y por los vértices anteriores. Luego, en cada paso del algoritmo hay a lo sumo Δ-1 colores prohibidos. Por lo tanto, se puede colorear G con Δ colores.

Referencias

  • Brooks, R. L. (1941), "On colouring the nodes of a network", Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37: 194–197

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Teorema de Bolzano-Weierstrass — Para el teorema de análisis real, véase Teorema de Weierstrass. En el análisis real, el teorema Bolzano–Weierstrass es un importante teorema que caracteriza los conjuntos secuencialmente compactos. Contenido 1 Enunciado 2 Demostración …   Wikipedia Español

  • Grado (teoría de grafos) — Para otros usos de este término, véase Grado. Un grafo con vértices etiquetados según su grado. El vértice aislado se etiqueta con 0, pues su grado es igual a cero. En Teoría de grafos, el grado o valencia de un vértice es el número de aristas… …   Wikipedia Español

  • 0,9 periódico — En matemáticas, 0,999... es el número decimal periódico que se demuestra denota[1] al número 1. En otras palabras, los símbolos 0,999... y 1 son dos representaciones distintas del mismo número real. Las demostraciones matemáticas de esta igualdad …   Wikipedia Español

  • Homosexualität im Film — Diese Liste enthält Filme mit homosexuellem Inhalt, sei es eine dargestellte Einzelperson in mehr als einer Nebenrolle oder eine gleichgeschlechtliche Begegnung. Chronologische Filmliste 1910er Jahre Anders als die Andern (D 1919) Regie: Richard… …   Deutsch Wikipedia

  • Cinéma de minuit — Le Cinéma de minuit est une émission de télévision française consacrée au cinéma dit « classique » ou ciné club, diffusée chaque dimanche soir sur France 3 aux alentours de minuit[1]. Elle a été créé le 28 mars 1976 sur FR3… …   Wikipédia en Français

  • Raoul Bott — Saltar a navegación, búsqueda Raoul Bott, FRS (n. 24 de septiembre de 1923 20 de diciembre de 2005) fue un matemático conocido por numerosas contribuciones fundamentales a la geometría. Había nacido en Budapest, se crió en Eslovaquia, pero pasó… …   Wikipedia Español

  • Ronald Mallett — Saltar a navegación, búsqueda Ronald L. Mallett, Ph.D. es un profesor de física en la Universidad de Connecticut Mallett nació en Roaring Spring, Pennsylvania, el 3 de marzo de 1945. Cuando tenía 10 años de edad su padre murió, a los 33 años, de… …   Wikipedia Español

  • Liste von Filmen mit homosexuellem Inhalt — Diese Liste enthält Filme mit homosexuellem Inhalt, sei es eine dargestellte Einzelperson in mehr als einer Nebenrolle oder eine gleichgeschlechtliche Begegnung. Chronologische Filmliste 1910er | 1920er | 1930er | 1940er | 1950er | 1960er |… …   Deutsch Wikipedia

  • Homosexualité au cinéma — L’homosexualité au cinéma consiste à montrer au cinéma des situations où l’homosexualité, sous toutes ses formes, est soit présente et non dissimulée ou soit, au contraire, peinte de façon subtile ou sous jacente. Longtemps quasi inexistante ou… …   Wikipédia en Français

  • Homosexualidad en el cine — La homosexualidad en el cine ha sido retratada de maneras muy diversas dependiendo de la época, del país, o de la mirada personal del director. Se ha reflejado en comedias, cine experimental, de terror, histórico, policiaco, de denuncia social,… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”