grafos - figuras planas

TEORIA DE GRAFOS

REPRESENTACIONES DE GRAFICAS.

ISOMORFISMO DE GRAFICAS.

GRAFICAS PLANAS.

REPRESENTACIONES

DE GRAFICAS.

TEORIA DE GRAFOS

REPRESENTACIONES DE GRAFICAS.

Consiste en un gráfico en el que los vértices se representan mediante puntos.Las conexiones se representarán de diferentes maneras, dependiendo de que el grafo sea orientado o no.

Para representar un grafo de una manera no gráfica, como por ejemplo en una computadora al analizar un grafo, se necesita una representación más formal. Existen dos métodos para representar una gráfica: Matriz de adyacencia: Se etiquetan en filas y columnas los vértices.Matriz de incidencia: Se etiquetan en las filas los vértices, y en las columnas las aristas.

MATRIZ DE ADYACENCIA

En este método para formar la matriz, primero elegimos los vértices siguiendo un orden cualquiera. A continuación etiquetamos las filas y las columnas de una matriz con los vértices ordenados. La entrada en esta matriz de adyacencia es uno si los vértices del renglón y la columna son adyacentes y cero en caso contrario. Llamamos vértices adyacentes a aquellos vértices que están formados por la misma arista. Llamamos aristas adyacentes a aquellas aristas que convergen en un mismo vértice.

Ejemplo de la matriz de adyacencia

A B C

A 2 1 1

B 1 0 2

C 1 2 0

En la matriz de adyacencia del grafico presentado en este ejemplo se va ha determinar si los vértices son adyacentes, y mediante que aristas.Ahora, una vez encontrada la matriz de adyacencia podemos calcular el grado de cada uno de los vértices.

Ejemplo de la matriz de adyacencia

A B C D E

A 0 1 0 0 0

B 1 0 0 1 0

C 1 0 0 1 0

D 0 1 1 1 0

E 0 0 1 0 0

Ejemplo de la matriz de adyacencia

A B C D E

A 0 0 0 1 0

B 0 0 1 0 0

C 0 1 0 0 0

D 0 1 1 0 1

E 1 1 0 0 0

MATRIZ DE INCIDENCIA

Los elementos de esta matriz están dados por la incidencia entre un vértice y una arista. Cuando existe esta incidencia se coloca uno, caso contrario cero. Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} ym=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm,B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario. PROPIEDADES Permite representar lazos y lados paralelos La columna con único valor diferente de 0 es un lazo Las columnas que no son lazos deben tener (2) unos La valencia de un vértice es igual a la suma de la fila

MATRIZ DE INCIDENCIA

a b c d e f g h

1 1 0 0 0 0 0 0 0

2 1 1 1 0 0 0 0 0

3 0 1 0 1 1 0 0 1

4 0 0 1 1 0 1 1 0

5 0 0 0 0 1 1 0 0

6 0 0 0 0 0 0 1 1

MATRIZ DE INCIDENCIA

La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente.Una fila compuesta sólo por ceros corresponde a un vértice aislado.

Ejemplo de la matriz de incidencia

e1 e2 e3 e4 e5

A 1 1 1 0 0

B 1 0 0 1 0

C 0 1 1 1 1

En la matriz de incidencia del gráfico presentado en este ejemplo va ha determinar la incidencia de las aristas con los vértices.Cuando una arista incide con un vértice toma el valor de uno, y cuando no incide el valor de cero.

LISTAS DE ADYACENCIA

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

LISTAS DE ADYACENCIA

LISTAS DE ADYACENCIA

ISOMORFISMO DE

GRAFICAS.

TEORIA DE GRAFOS

Isomorfismo de gráficas

Dos grafos son isomorfos si existe correspondencia uno a uno entre los nodosde los dos grafos, y además conservan la adyacencia entre los nodos así como la dirección de los ejes, si existen.De acuerdo con la definición de isomorfismo nos damos cuenta que un par cualquiera de nodos que esta unido por un eje debe de tener los nodos correspondientes en el otro grafo también unidos por un eje, así mismo debe existir una correspondencia uno a uno entre los ejes.

Isomorfismo de gráficas

Dos graficas simples G1 y G2 son isomorfas si y solo si para cierto orden de sus vértices las matrices de adyacencia son iguales.

A B C D E

A 0 1 0 1 0

B 1 0 1 1 1

C 0 1 0 1 1

D 1 1 1 0 0

E 0 1 1 0 0

Isomorfismo de gráficas

A B C D E

A 0 1 0 1 1

B 1 0 0 1 0

C 0 0 0 1 1

D 1 1 1 0 1

E 1 0 1 1 0

Isomorfismo de gráficas

A B C D E

A 0 1 0 1 0

B 1 0 1 1 1

C 0 1 0 1 1

D 1 1 1 0 0

E 0 1 1 0 0

A B C D E

A 0 1 0 1 1

B 1 0 0 1 0

C 0 0 0 1 1

D 1 1 1 0 1

E 1 0 1 1 0

RTA/ Estas no son graficas isomorfas

Isomorfismo de gráficas

A B C D

A 0 1 1 1

B 1 0 1 1

C 1 1 0 1

D 1 1 1 0

A B C D

A 0 1 1 1

B 1 0 1 1

C 1 1 0 1

D 1 1 1 0

RTA/ Son isomorfos

GRAFICAS PLANAS.

TEORIA DE GRAFOS

GRAFICAS PLANAS

Una gráfica puede pensarse como un diagrama que consiste de una colección de puntos y líneas que se unen entre sí. Esta idea puede caracterizarse definiendo a cualquier gráfica G como un par de conjuntos (V(G),E(G)) donde V(G) es un conjunto finito no vacío de elementos llamados vértices y E(G) es un conjunto finito de pares no ordenados de elementos de V(G) llamados líneas o aristas.

A continuación presentamos dos ejemplos de gráficas que si bien parecen bastante diferentes a primera vista son esencialmente iguales (isomorfas).

GRAFICAS PLANAS

En la gráfica de la figura 1 hay dos aristas que se intersectan en un punto que no es un vértice de ésta, mientras que en la segunda gráfica las aristas no se intersectan más que en un vértice. Es de notarse que a pesar de que dos gráficas puedan parecer tan distintas posean la misma estructura; observemos que ambas tienen el mismo conjunto de puntos y vértices, es decir, son la “misma” gráfica pero dibujada de diferente manera.

GRAFICAS PLANAS

Dependiendo de cómo dibujemos una gráfica, ésta puede ser plana si puede ser dibujada en el plano de manera que sus aristas no se intersectan geométricamente mas que en un vértice. Por ejemplo, en la figura anterior tenemos dos formas de dibujar la misma gráfica: en la primera el dibujo no es una gráfica plana, mientras que en la segunda si.

GRAFICAS PLANAS

Cuando una gráfica es plana, es decir, que podemos dibujarla en el plano sin que sus aristas se intersectan, entonces todos los puntos del plano que no están en G forman caras o regiones.

GRAFICAS PLANAS

Regiones de un grafo plano:

Una representación plana de un grafo divide el plano en regiones, entre ellas una región no acotada.

GRAFICAS PLANAS

Existen teoremas que nos ayudan a determinar si una gráfica es plana o no, los teoremas son:

• TEOREMA DE EULER.

• TEOREMA DE KURATOWSKI .

GRAFICAS PLANASTeorema de Euler

Una gráfica plana, divide al plano en distintas regiones llamadas caras. Si se denota el número de caras por C, el número de vértices por V y el número de aristas por A, en la figura se tiene que C = 4, V = 4 y A = 6.

En toda gráfica conexa y plano que esté representado se verifica que el número de caras más el de vértices menos el de aristas vale 2. Es decir

C – A + V = 2.

GRAFICAS PLANASTeorema de Kuratowski

Un grafo es plano si no contiene como subgrafo a K5 (grafo completo de 5 vértices) ni a K3,3 (bipartito completo de 6 vértices).

GRAFICAS PLANASTeorema de Kuratowski

En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es plano. Sin embargo, existe un algoritmo rápido para este problema: dado un grafo de n vértices y e el número de aristas, es posible determinar si el grafo es plano o no, utilizando los dos teoremas siguientes:

Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6

Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4

GRAFICAS PLANASTeorema de Kuratowski

El grafo K3,3, por ejemplo, tiene 6 vértices, 9 aristas y ningún ciclo de longitud 3. Por el teorema 2, no puede ser plano. Nótese que estos teoremas están construidos con una implicación unidireccional (si), y no bicondicional (si y solo si) y por tanto, solamente pueden ser usados para probar que el grafo no es plano, pero no que sea plano.

GRAFICAS PLANASTeorema de Kuratowski

Ejemplo: El grafo de Petersen no es plano, porque contiene un subgrafo de K3,3.

GRAFICAS PLANASEjemplos

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

GRAFICAS PLANASEjemplo

Vértices = 5, Aristas = 7, Regiones = 4

Aplicando Euler: R – A + V = 2 ó R = A – V + 2

-> 4 – 7 + 5 = 2 ó 4 = 7 - 5 + 2

2 = 2 ó 4 = 4

GRAFICAS PLANASAplicación

Las gráficas se utilizan al dibujar circuitos integrados impresos en chips de silicón, que son usados en dispositivos electrónicos, ésta es una de las aplicaciones más importantes de las gráficas planas, ya que estos chips deben estar diseñados de tal modo que las porciones conductoras no se crucen entre si.