Se dice que una gráfica es plana si se puede dibujar en un plano de modo que ninguna arista se cruce.

Ejemplo: El gráfico que se muestra en la figura es un gráfico plano.

expresiones lambda de java

Región de un gráfico: Considere un gráfico plano G = (V, E). Una región se define como un área del plano que está limitada por bordes y no se puede subdividir más. Un gráfico plano divide los planes en una o más regiones. Una de estas regiones será infinita.

Región finita: Si el área de la región es finita, entonces esa región se llama región finita.

Región infinita: Si el área de la región es infinita, esa región se llama región infinita. Un gráfico plano tiene sólo una región infinita.

Ejemplo: Considere el gráfico que se muestra en la Fig. Determine el número de regiones, regiones finitas y una región infinita.

Solución: Hay cinco regiones en el gráfico anterior, es decir, r₁,r₂,r₃,r₄,r₅.

Hay cuatro regiones finitas en el gráfico, es decir, r₂,r₃,r₄,r₅.

Sólo hay una región finita, es decir, r₁

Propiedades de los gráficos planos:

1. Si un gráfico plano conectado G tiene e aristas y r regiones, entonces r ≦ Es.
2. Si un gráfico plano conectado G tiene e aristas, v vértices y r regiones, entonces v-e+r=2.
3. Si un gráfico plano conectado G tiene e aristas y v vértices, entonces 3v-e≧6.
4. Un gráfico completo K_nortees plano si y sólo si n<5.< li>
5. Un gráfico bipartito completo K_Minnesotaes plano si y sólo si m3.

Ejemplo: Demuestre que la gráfica completa K₄es plano.

Solución: El gráfico completo K₄contiene 4 vértices y 6 aristas.

Sabemos que para un gráfico plano conectado 3v-e≧6. Por lo tanto, para K₄, tenemos 3x4-6=6 que satisface la propiedad (3).

enumeraciones java

Así K₄es un gráfico plano. Por lo tanto probado.

Gráfico no plano:

Se dice que un gráfico no es plano si no se puede dibujar en un plano de manera que no se crucen aristas.

Ejemplo: Los gráficos que se muestran en la figura son gráficos no planos.

Estos gráficos no se pueden dibujar en un plano para que no se crucen aristas, por lo que son gráficos no planos.

Propiedades de los gráficos no planos:

Un gráfico es no plano si y sólo si contiene un subgrafo homeomorfo a K₅o k_3,3

cola de prioridad de java

Ejemplo 1: Demuestre que K₅es no plano.

Solución: El gráfico completo K₅contiene 5 vértices y 10 aristas.

Ahora, para un gráfico plano conectado 3v-e≧6.

Por lo tanto, para K₅, tenemos 3 x 5-10=5 (lo cual no satisface la propiedad 3 porque debe ser mayor o igual a 6).

Así, K₅es un gráfico no plano.

Ejemplo2: Demuestre que las gráficas que se muestran en la figura no son planas encontrando un subgrafo homeomorfo a K₅o k_3,3.

Solución: Si quitamos los bordes (V₁,EN₄),(EN₃,EN₄)y V₅,EN₄) la gráfica G₁, se vuelve homeomorfo a K₅.Por tanto, no es plano.

Si quitamos el borde V_2,V7) la gráfica G₂se vuelve homeomorfo a K_3,3.Por lo tanto, es no plano.

Coloración de gráficos:

Supongamos que G= (V,E) es un gráfico sin aristas múltiples. Una coloración de vértices de G es una asignación de colores a los vértices de G de modo que los vértices adyacentes tengan colores diferentes. Un gráfico G es M-Colorable si existe una coloración de G que utiliza M-Colores.

Coloración adecuada: Una coloración es adecuada si dos vértices adyacentes u y v tienen colores diferentes; de lo contrario, se llama coloración impropia.

creación de tabla de oráculo

Ejemplo: Considere el siguiente gráfico y coloree C={r, w, b, y}. Coloree el gráfico correctamente usando todos los colores o menos colores.

El gráfico que se muestra en la figura tiene un mínimo de 3 colores, por lo tanto x(G)=3

Solución: La figura muestra el gráfico correctamente coloreado con los cuatro colores.

La figura muestra el gráfico correctamente coloreado con tres colores.

Número cromático de G: El número mínimo de colores necesarios para producir una coloración adecuada de un gráfico G se llama número cromático de G y se denota por x(G).

Ejemplo: El número cromático de K._nortees n.

Solución: Una coloración de K_norteSe puede construir usando n colores asignando diferentes colores a cada vértice. No se pueden asignar los mismos colores a dos vértices, ya que cada dos vértices de este gráfico son adyacentes. De ahí el número cromático de K_norte= norte.

Aplicaciones de colorear gráficos

Algunas aplicaciones de coloración de gráficos incluyen:

• Asignación de registros
• Mapa para colorear
• Comprobación de gráficos bipartitos
• Asignación de radiofrecuencia móvil
• Elaborar un horario, etc.

Enunciar y demostrar el teorema del apretón de manos.

Teorema del apretón de manos: La suma de grados de todos los vértices de un gráfico G es igual al doble del número de aristas del gráfico.

Matemáticamente se puede expresar como:

∑_v∈Vgrados(v)=2e

Prueba: Sea G = (V, E) una gráfica donde V = {v₁,en₂, . . . . . . . . . .} sea el conjunto de vértices y E = {e₁,Es₂. . . . . . . . . .} sea el conjunto de aristas. Sabemos que cada arista se encuentra entre dos vértices, por lo que proporciona grado uno a cada vértice. Por tanto, cada arista contribuye con el grado dos del gráfico. Entonces la suma de los grados de todos los vértices es igual al doble del número de aristas en G.

Por tanto, ∑_v∈Vgrados(v)=2e

números romanos 1 100