LengAut_LemEncajadas

Lema de las encajadas

Facilitador: Saúl Olaf Loaiza Melendez

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

2021/2022

Lenguajes y AutómatasGráfos

Figura 1. Grafo no dirigido G

Tamaño

Orden

Orden y tamaño

Ejemplo

Ejemplo

En un grafo dirigido G = (V,E), para cualquier lado e(i, j) se dice que e es incidente en los vértices i y j, los cuales son sus vértices extremos, i es adyacente hacia j, mientras que j es adyacente desde i. Además, el vértice i es el origen o fuente del lado (i, j) y el vértice j es el término o vértice terminal de dicho lado.En un grafo no dirigido G(V, E), para todo lado e{i, j} se dice que e es incidente en los vértices i y j, los cuales son sus vértices extremos. Además, se dice que los vértices i y j son vértices adyacentes.Por tanto, en cualquiera de los dos casos, se puede decir que dos vértices son adyacentes si están unidos por un mismo lado.

Incidencia y adyacencia

Figura 4. Grafo nulo G

Se dice que un grafo (dirigido o no dirigido) G(V, E) es nulo si tiene todos sus vértices aislados. Por vértice aislado se entiende aquel que no es extremo de ningún lado o que no tiene ningún lado incidente sobre sí.En este caso, se tiene que E es vacío, es decir, que |E|=0

Grafo Nulo

Ejemplo

En un grafo (dirigido o no dirigido) G(V, E), cuando dos o más lados distintos son incidentes al mismo par de vértices, estos reciben el nombre de lados paralelos.Por su parte, un lado de la forma (i, i) que inicia y termina en el mismo vértice se conoce como lazo; es decir, el vértice es adyacente consigo mismo.

Lados paralelos y lazos

Ejemplo

Un grafo (dirigido o no dirigido) G = (V, E) que no tiene lazos ni lados paralelos recibe el nombre de grafo simple.

Grafo simple

Ejemplo

En un grafo no dirigido, G = (V, E), se llama valencia (o grado) de un vértice, v, al número de incidentes en v, y se denota como g(v).Además, se tiene que la suma de las valencias de todos los vértices de un grafo no dirigido, G(V, E), es igual al doble del número de lados; es decir, el tamaño |E| del grafo, siempre y cuando el grafo no contenga lazos.Conocido tambien como el lema de las encajadas, que se cumple para todos los grafos.

Velencia de un vértice

En esta actividad se reforzó los conceptos orden, tamaño, incidencia, adyacencia y grado. Todos estos con respecto a los vertices de un grafo.Una de las características que siempre se cumplen en los grafos es el lema de las encajadas, con este lema más adelante se puede realizar grafos de acuerdo al grado de cada vértice.Figura 7. Lema de las encajadas.Figuf

Resumen

Ramón Espinoza, A. (2017). Capítulo XVII Grafos dirigidos En Matemáticas Discretas (2da. ed., pp. 429-451). AlfaomegaVillalpando Becerra, J. F., & Gacría Sandoval, A.(Eds.). (2014). Capítulo 6, Teoría de grafos. En Matemáticas discretas aplicaciones y ejercicios (1ra ed., pp. 185-233) Grupo Editorial Patria.EPP, S. (2012). Capítulo 10 Grafos y árboles En Matemáticas discretas con aplicaciones (4ta. ed., pp. 625-675). Cengage Learning.Johnsonbaugh R. (2005). Capítulo 8 Teoría de gráficas En Matemáticas discretas (6ta. ed., pp. 318-377). Educación Pearson.Tremblay, J. P. & Manohar. R. (Eds.). (1999). Capítulo 5 Teoría de gráficas En Matemáticas discretas con aplicación a las ciencias de la computación (1ra. ed., pp. 463-488). CECSA Figufds

Referencias

Esto es un párrafo listo para contener creatividad, experiencias e historias geniales.

¡Gracias!