in

Gráficos planos y no planos – javatpoint

planar and non planar graphs

Se dice que una gráfica es plana si se puede dibujar en un plano de modo que ningún borde se cruce.

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

Gráficos planos y no planos
Gráficos planos y no planos

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á delimitada 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 solo una región infinita.

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

Gráficos planos y no planos

Solución: Hay cinco regiones en el gráfico anterior, es decir, r1, r2, r3, r4, r5.

Hay cuatro regiones finitas en el gráfico, es decir, r2, r3, r4, r5.

Solo hay una región finita, es decir, r1

Propiedades de los gráficos planos:

  1. Si un grafo plano conectado G tiene e bordes y r regiones, entonces r ≤Gráficos planos y no planosmi.
  2. Si un grafo plano conectado G tiene aristas e, v vértices yr regiones, entonces v-e + r = 2.
  3. Si un gráfico plano conectado G tiene aristas e y v vértices, entonces 3v-e≥6.
  4. Un gráfico completo Knorte es un plano si y solo si n
  5. Un gráfico bipartito completo KMinnesota es plano si y solo si m3.

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

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

Sabemos que para un grafo plano conectado 3v-e≥6, de ahí que K4, tenemos 3×4-6 = 6 que satisface la propiedad (3).

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

Gráfico no plano:

Se dice que una gráfica no es plana si no se puede dibujar en un plano de modo que ningún borde se cruce.

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

Gráficos planos y no planos

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

Propiedades de los gráficos no planos:

Un gráfico no es plano si y solo si contiene un subgrafo homeomorfo a K5 o K3,3

Ejemplo 1: Muestra que K5 no es plano.

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

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

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

Por lo tanto, K5 es un gráfico no plano.

Ejemplo 2: Demuestre que las gráficas que se muestran en la figura no son planas al encontrar un subgrafo homeomorfo a K5 o K3,3.

Gráficos planos y no planos
Gráficos planos y no planos

Solución: Si quitamos los bordes (V1, V4), (V3, V4)y V5, V4) el gráfico G1, se vuelve homeomorfo a K5Por lo tanto, no es plano.

Si quitamos el borde V2, V7) el gráfico G2 se vuelve homeomorfo a K3,3Por lo tanto, no es plano.

Coloración de gráficos:

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

Coloración adecuada: Una coloración es adecuada si dos vértices adyacentes uyv tienen colores diferentes; de lo contrario, se denomina coloración inadecuada.

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

Gráficos planos y no planos

El gráfico que se muestra en la figura es 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.

Gráficos planos y no planos

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

Gráficos planos y no planos

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 denomina número cromático de G y se denota por x (G).

Ejemplo: El número cromático de Knorte es n.

Solución: Una coloración de Knorte se 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 Knorte= n.

Aplicaciones de la coloración de gráficos

Algunas aplicaciones de la 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
  • Hacer una tabla de tiempo, etc.

Enuncie y demuestre el teorema del apretón de manos.

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

Matemáticamente se puede afirmar como:

v∈Vgrados (v) = 2e

Prueba: Sea G = (V, E) una gráfica donde V = {v1, v2,. . . . . . . . . .} ser el conjunto de vértices y E = {e1,mi2 . . . . . . . . . .} ser el conjunto de aristas. Sabemos que cada borde se encuentra entre dos vértices, por lo que proporciona un grado uno a cada vértice. Por lo tanto, cada borde aporta un grado dos para el gráfico. Entonces, la suma de grados de todos los vértices es igual al doble del número de aristas en G.

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


Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Métodos de cadena de JavaScript

reactjs

Tutorial de ReactJS