Representación Grafica de Grafos

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa

Universidad Nacional Experimental Politécnica De la Fuerza Armada Nacional Bolivariana
UNEFA-Núcleo Miranda Extensión Santa Teresa del Tuy
Carrera: Ing. Sistemas Semestre: 5to Sección: 05S-2615-D1
Materia: Teoría de Grafos
Representación
Gráfica de Grafos
Profesor: Estudiante:
Franklin Perdomo Manuel Ortiz C.I:25.792.247
Santa Teresa del Tuy: 03-12-2019

Índice
Introducción. . . . . . . . . . . Pg.3
Representación de los Grafos . . . . . . . . Pg.4
Estructura de Lista . . . . . . . . . Pg.4
Representación Matricial . . . . . . . . Pg.5-6
Caminos Y Ciclos . . . . . . . . . Pg.6-7
Sub-Grafos . . . . . . . . . . Pg.7-8
Conclusión. . . . . . . . . . . Pg.9
Bibliografía. . . . . . . . . . . Pg.10
Pg. 2
Introducción
Primero que nada la Representación Gráfica de Grafos no es hacer un dibujo que
corresponda al grafo y ya, es mucho más que eso, ya que dependiendo del mismo grafo
cambian muchos aspectos, como si es una de las representaciones del tipo matricial o de
lista o si solo con una de las representación es suficiente para hacer el grafo, hay pasos a
seguir como consejo que ayudan a identificar esto de manera simple.
Pg. 3
Representación de los Grafos
Existen diferentes formas de representar un grafo, además de la geométrica y muchos

métodos para almacenarlos en una computadora. La estructura de datos usada depende de
las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más
sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una
combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un
eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden
consumir grandes cantidades de memoria.
Estructura de Lista
Lista de incidencia: Las aristas son representadas con un vector de pares (ordenados, si el
grafo es dirigido), donde cada par representa una de las aristas.
Lista de adyacencia: Cada vértice tiene una lista de vértices los cuales son adyacentes a él.
Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de
B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
Si el grafo es no dirigido, cada entrada es un conjunto o multi-conjunto de dos vértices
conteniendo los dos extremos de la arista correspondiente. Si el grafo es dirigido, cada
entrada es una tupla de dos nodos, uno denotando el nodo fuente y el otro denotando el
nodo destino del arco correspondiente.
Lista de grados: También llamada secuencia de grados o sucesión gráfica de un grafo no-
dirigido es una secuencia de números, que corresponde a los grados de los vértices del
grafo.
Pg. 4
Representación Matricial
El uso de matrices para representar sistemas de ecuaciones, relaciones o grafos permite una
rápida y una clara manipulación de la información, así como el de determinar algunas
propiedades de los grafos que de otra manera serían más difíciles el manejo de matrices, ya
que se pueden tratar como arreglos o lista doblemente ligadas.
A continuación se describen las representaciones matriciales de los grafos:
Matriz de Adyacencia: Es una matriz cuadrada en la cual los vértices del grafo se indica
como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y
las columnas de la matriz.se coloca un 1 como elemento de la matriz cuando existe una
relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.
Propiedades: Es cuadrada y simétrica. La suma de cada fila o columna es el grado de

vértice correspondiente. La diagonal es nula
Matriz de Incidencia: Una matriz que está compuesta por unos y ceros, en la que se
representan los nodos unidos por las aristas. Cada arista une dos y nada más que dos nodos.
En general, las matrices de incidencia no son usadas computacionalmente, pero sirven
como ayuda conceptual.
El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista,
vértice] contiene la información de la arista (1 – conectado, 0 – no conectado)
Pg. 5
Nota: No tiene por qué ser ni cuadrada ni simétrica.
Caminos Y Ciclos
En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un
polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a
excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo
ciclo de n vértices se denota 𝐶𝑛. El número de vértices en un grafo 𝐶𝑛 es igual al número
de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas
incidentes.
Si 𝐺(𝑉, 𝐴) es un ciclo 𝐶𝑛, el grafo tiene n vértices 𝑉 = {𝑣1 , 𝑣2 . . . 𝑣𝑛 } y n de aristas
formadas de la siguiente manera:
𝐴 = {{𝑣𝑖 , 𝑣𝑖 + 1}⎹ 𝑖 = 1, . . . , 𝑛}⋃{𝑣𝑛 , 𝑣1 }

Camino: Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe
una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su
recorrido.
Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el
primero y el último.
La longitud de un camino es el número de aristas que usa dicho camino, contando aristas
recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2,
5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.
Camino euleriano: Un camino euleriano en un grafo es un camino que usa cada arista una
y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es
dual a la de camino hamiltoniano. Un camino euleriano recorre todas las aristas
exactamente una vez (puede repetir vértices).
Camino hamiltoniano: Existe un concepto dual al de camino/ciclo Euleriano. Un camino

hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.
Un camino hamiltoniano recorre todos los vértices exactamente una vez.
Pg. 6
Ciclo: Un Ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los
ciclos de longitud 1 se denominan lazos o bucles. Un ciclo simple es un ciclo que tiene
como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.
Ciclo euleriano: Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y sólo
una vez. Un ciclo euleriano pasa por todas las aristas exactamente una vez, regresando al
punto de partida.
Ciclo hamiltoniano: Un ciclo hamiltoniano en un grafo es un ciclo que visita cada vértice
una y sólo una vez. Un ciclo hamiltoniano pasa por todos los vértices exactamente una vez,
regresando al punto de partida.
SUB-GRAFOS
Un sub-grafo de un grafo G es un grafo cuyo conjunto de vértices es un subconjunto del de
G, cuyo conjunto de aristas es un subconjunto del conjunto de las aristas de G, y tal que la
aplicación w es la restricción de la aplicación de G.
Un sub-grafo se define como un grafo con vértices y aristas que son un subconjunto de un
grafo padre.
Un problema común en la lógica computacional es el Problema de Isomorfismo de Sub-
grafos, en el mismo se tienen dos grafos G1 y G2, y se desea saber si existe un sub-grafo en
G2 que sea isomorfo a G1.
Consideremos los siguientes grafos, el grafo G1 sería el siguiente:
Pg. 7
El grafo G2 sería el siguiente:
Entonces, en este caso se podría decir que la respuesta al problema es afirmativa, ya que las
aristas entre los vértices A, B y C formarían un sub-grafo que es isomorfo a G1. En caso de
no existir este sub-grafo isomorfo, la respuesta sería obviamente negativa.
Pg. 8
Conclusión
Se puede entender de la información ya antes vista que la representación gráfica de grafos
tiene diferentes aspectos como formas de hacerlos, dependen mayormente de aristas y
vértices para descifrar con que estructura se puede representar el grafo, también las
diferencias en las uniones de los vértices y aristas que crean caminos o ciclos en los grafos
y en los sub-grafos que puedan tener los grafos.
Pg. 9
Bibliografía
Matemática Discreta. S/f. Representación de los Grafos. [Documento en línea]. En

https://matematicadicreta.wordpress.com/matematica-discreta-2/representacion-de-los-
grafos/ [Consulta: Noviembre 30, 2019].
Matemática Discreta. S/f. Estructura de Lista. [Documento en línea]. En

https://matematicadicreta.wordpress.com/matematica-discreta-2/representacion-de-los-
grafos/ [Consulta: Noviembre 30, 2019].
Petul, G. 2011. Representación Matricial [Documento en línea]. En http://teoriadegrafos-

isc.blogspot.com/2011/12/representacion-de-los-grafos.html [Consulta: Noviembre 30,
2019].
Unknown. 2014. Matriz de Adyacencia. [Documento en línea]. En http://mate-

booleanas.blogspot.com/2014/05/representacion-matricial.html [Consulta: Noviembre 30,
2019].
Unknown. 2014. Matriz de Incidencia. [Documento en línea]. En http://mate-

booleanas.blogspot.com/2014/05/representacion-matricial.html [Consulta: Noviembre 30,
2019].
Carballido, P. 2015. Caminos y Ciclos. [Documento en línea]. En

http://matematicasidscretastemario1.blogspot.com/2015/12/caminos-y-ciclos.html
[Consulta: Noviembre 30, 2019].
Wikipedia. S/f. Caminos y Ciclos. [Documento en línea]. En

https://es.wikipedia.org/wiki/Anexo:Glosario_de_teor%C3%ADa_de_grafos [Consulta:
Noviembre 30, 2019].
Suárez, A. 2011. Sub-Grafos. [Documento en línea]. En

https://es.slideshare.net/asdrubal1990/grafos-bipartitos-y-subgrafos [Consulta: Noviembre
30, 2019].
Pg. 10

Representación Grafica de Grafos

Cargado por

Copyright:

Formatos disponibles

Representación Grafica de Grafos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Representación Grafica de Grafos

Cargado por

Copyright:

Formatos disponibles

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Defensa

Franklin Perdomo Manuel Ortiz C.I:25.792.247

Santa Teresa del Tuy: 03-12-2019

Representación de los Grafos . . . . . . . . Pg.4

Estructura de Lista . . . . . . . . . Pg.4

Representación Matricial . . . . . . . . Pg.5-6

Caminos Y Ciclos . . . . . . . . . Pg.6-7

Existen diferentes formas de representar un grafo, además de la geométrica y muchos

Propiedades: Es cuadrada y simétrica. La suma de cada fila o columna es el grado de

𝐴 = {{𝑣𝑖 , 𝑣𝑖 + 1}⎹ 𝑖 = 1, . . . , 𝑛}⋃{𝑣𝑛 , 𝑣1 }

Camino hamiltoniano: Existe un concepto dual al de camino/ciclo Euleriano. Un camino

Matemática Discreta. S/f. Representación de los Grafos. [Documento en línea]. En

Matemática Discreta. S/f. Estructura de Lista. [Documento en línea]. En

Petul, G. 2011. Representación Matricial [Documento en línea]. En http://teoriadegrafos-

Unknown. 2014. Matriz de Adyacencia. [Documento en línea]. En http://mate-

Unknown. 2014. Matriz de Incidencia. [Documento en línea]. En http://mate-

Carballido, P. 2015. Caminos y Ciclos. [Documento en línea]. En

Wikipedia. S/f. Caminos y Ciclos. [Documento en línea]. En

Suárez, A. 2011. Sub-Grafos. [Documento en línea]. En

También podría gustarte