• ¿QUE SON LOS GRAFOS?
Un grafo esta definido como un tipo muy general de estructura formado por un
par ordenado G= (V, E), donde V= (v1, v2, v3…) comprende a un conjunto de
vértices y E = ( e1, e2, e3 …) a un conjunto de aristas, un grafo es una
colección de vértices y de aristas que unen estos vértices. Los vértices los
dibujaremos como puntos (o pequeños círculos) sobre el plano; las aristas
serán líneas que unen estos puntos.
• ¿CUÁLES SON LOS ELEMENTOS DE UN GRAFO?
Aristas: Son las líneas que unen los vértices de un grafo.
Aristas adyacentes: Dos aristas son adyacentes si convergen en el mismo
vértice.
Aristas paralelas: Dos aristas son paralelas si los vértices iniciales y finales
son el mismo.
Aristas cíclicas: Aristas que parten de un vértice para entrar en el mismo.
Cruce: Punto donde dos aristas se cruzan.
Vértices: Los vértices son los elementos que forman un grafo. Cada uno lleva
asociada una valencia característica según la situación, que se corresponde
con la cantidad de aristas que confluyen en dicho vértice.
Camino: Se denomina camino a un conjunto de vértices interconectados por
aristas. Dos vértices están conectados si hay un camino entre ellos.
• ¿CUÁNTOS TIPOS DE GRAFOS EXISTEN?
Grafo simple: O simplemente grafo es aquel que acepta una sola arista
uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista
cualquiera es la única que une dos vértices específicos. Es la definición
estándar de un grafo.
Multigrafo o pseudografo: Es el que acepta más de una arista entre dos
vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos
simples son una subclase de esta categoría de grafos. También se les llama
grafos general.
Grafo orientado: grafo dirigido o dígrafo. Son grafos en los cuales se ha
añadido una orientación a las aristas, representada gráficamente por una
flecha.
Grafo etiquetado: Grafos en los cuales se ha añadido un peso a las aristas
(número entero generalmente) o un etiquetado a los vértices.
Grafo aleatorio: Grafo cuyas aristas están asociadas a una probabilidad.
Hipergrafo: Grafos en los cuales las aristas tienen más de dos extremos, es
decir, las aristas son incidentes a 3 o más vértices.
Grafo infinito: Grafos con conjunto de vértices y aristas de cardinal infinito.
Grafo plano: Los grafos planos son aquellos cuyos vértices y aristas pueden ser
representados sin ninguna intersección entre ellos. Podemos establecer que un
grafo es plano gracias al Teorema de Kuratowski.
Grafo regular: Un grafo es regular cuando todos sus vértices tienen el mismo
grado de valencia.
Grafo dual: El grafo dual G´ de un grafo G (plano), es aquel que tiene un vértice
por cada región de G, y una arista por cada arista en G uniendo dos regiones
vecinas.
• EXPONGA 1 EJEMPLO DE GRAFOS SIMPLES Y 1 DE GRAFO NO
SIMPLES
NO SIMPLE
SIMPLE
• ¿A QUÉ SE DENOMINA LAZO?
Es aquella arista que sale de un vértice
y regresa al mismo vértice
• ¿A QUÉ SE DENOMINA VERTICE AISLADO?
Vértice Aislado: Es un vértice
de grado cero
¿A QUÉ SE DENOMINA ARISTAS PARALELAS?
Aristas Paralelas: estas son dos
aristas si el vértice inicial y el final son uno mismo
• Bibliografía
Anonimo. (2015). Elementos y Características de los Grafos. 2020, diciembre 9, de Mátematicas
discretas Recuperado de https://sites.google.com/site/matedicreta/6-1-elementos-y-
caracteristicas-de-los-grafos/
Anonimo. (2017). Teoría de grafos. 2020, diciembre 9, de Mátematicas.1 Recuperado de
Anonimo. (2015). Elementos y Características de los Grafos. 2020, diciembre 9, de Mátematicas
discretas Recuperado de https://sites.google.com/site/matedicreta/6-1-elementos-y-
caracteristicas-de-los-grafos/
WIkipedia. (15/09/2020). Teoría de grafos. 2020, diciembre 9, de Wikipedia Recuperado de
Anonimo. (2015). Elementos y Características de los Grafos. 2020, diciembre 9, de Mátematicas
discretas Recuperado de https://sites.google.com/site/matedicreta/6-1-elementos-y-
caracteristicas-de-los-grafos/
