Mmdi U2 A1 Ulmh

Nombre del alumno: Ulises Manzano Hernández
Matricula: ES1921005869
Grupo: MT – MMDI – 2001 – B1 – 003
Materia: Matemáticas Discretas
Carrera: Licenciatura en Matemáticas
Nombre de la Actividad: Actividad 1 “Conceptos Fundamentales de la Teoria

de Grafos”
Nombre de la escuela: Universidad Abierta y a Distancia de México
Nombre del profesor: Jose Eduardo García Mendiola
Fecha de entrega: 10 al 16 de Febrero de 2020

Actividad del Foro
Investigar los siguientes conceptos sobre la Teoría de Gráficas.
1. Gráfica (Grafo). – En matemáticas y ciencias de la computación, un grafo
es un conjunto de objetos llamdos vertices o nodos unidos por enlaces
llamados aristas o arcos, que permiten representar relaciones binarias
entre elementos de un conjunto. Un gráfo es un par ordenado 𝐺 = {𝑉, 𝐸}.
En donde 𝑉 es un conjunto de vértices o nodos, y 𝐸 es un conjunto de
aristas o arcos, que se relacionan estos nodos.
2. Digrafo. – Tambien llamado grafo dirigido es un tipo de grafo en el cual

las aristas tienen un sentido definido, a diferencias del grafo no dirigido,
en el cual las aristas son relaciones simétricas y no apuntan en ningún
sentido. Al igual que en el grafo generalizado, el grafo dirigido por un par
de conjuntos 𝐺 = {𝑉, 𝐸}, donde:
• 𝑉 ≠ 0, un conjunto no vacío de objetos simples llamados vértices
o nodos.
• 𝐸 ⊆ {(𝑎, 𝑏) ∈ 𝑉 × 𝑉: 𝑎 ≠ 𝑏} es un conjunto de pares ordendos de
elementos de 𝑉 denominados aristas o arcos, donde por definición
un arco va del primer nodo al segundo nodo dentro del par.
Un arco 𝑒 = (𝑥, 𝑦) se considera dirigido desde 𝑥 hacia 𝑦. Otra notación
valida es 𝑒 =< 𝑥, 𝑦 >. En ambos casos, el vertice 𝑥 cumple un rol de
emisor y el vertice 𝑦 uno de receptor.
3. Orden de una gráfica. – Se llama asi a su número de vertices, |𝑉|.

4. Tamaño de una gráfica. – El Tamaño de una gráfica es el número de
bordes.
5. Grado de un vertice. – es el número de aristas incidentes al vertice. El

grado de un vértice 𝑥 es denotado por 𝑔(𝑥) (aunque también usa 𝛿(𝐺),
y del ingles 𝑑(𝑥) y deg(𝑥)). El grado máximo de un grafo 𝐺 es denotado
por ∆(𝐺) y el grado mínimo de un grafo 𝐺 es denotado por 𝛿(𝐺). Un
vertice con grado 0 es un vértice aislado. Un grafo formado
exclusivamente por vértices aislados es un grafo vacío. Un grafo donde
todos los vértices tienen el mismo grado es un grafo regular, y un grafo
no dirigido de 𝑛 vertices en que todos los vértices tiene grado 𝑛 − 1 es
un grafo completo.
6. Grafo Completo. – En teoria de grafos, es un grafo simple donde cada

par de vértices está conectado por una arista. Un grafo completo de 𝑛
𝑛(𝑛−1)
vertices tiene arista, y se denota 𝐾𝑛 . Es un grafo regular con todos
2
sus vértices de grado 𝑛 − 1. La única forma de hacer que un grafo
completo se torne disconexo a través de la eliminación de vértices, sería
eliminandolos todos.
7. Camino. – Es una sucesión de vértices y aristas dentro de un grafo, que

empieza y termina en vertices, tal que cada vértice es incidente con las
aristas que le siguen y le preceden en la secuencia. 2 vertices están
conectados o son accesibles si existen un camino que forma una
trayectoria para llegar de uno al otro; en caso contrario, los vértices están
desconectados o bien inaccesibles.
8. Ciclo. – Es un grafo que consiste en un camino simple cerrado, es decir,

en el que no se repite ningún vértice, salvo el primero con el último. Un
grafo de 𝑛 vertices de denota 𝐶𝑛 . El número de vértices en un grafo ciclo
es igual al número de aristas. En su versión más común, como grafo no
dirigido, cada vértice tiene grado 2, por lo que es un grafo 2 – regular; en
su versión dirigida, en cambio, se trata de un grafo 1 – regular.
9. Paseo. – Es una lista 𝑣0 , 𝑒1 , 𝑣1 , …, 𝑒𝑘 , 𝑣𝑘 de vertices y aristas tal que
para cada 𝑖 ∈ {1, … , 𝑘}, la aristas 𝑒𝑖 tiene extremos 𝑣𝑖−1 y 𝑣𝑖 .
10. Trayectorias. – En un grafo es una secuencia de aristas que

permiten viajar de un vértice a otro de manera continua. La longitud de
un trayectoria es su número de aristas. A una trayectoria de 𝑘 aristas se
le llama 𝑘 – trayectoria. A una trayectoria que comienza y termina en el
mismo vértice se le llama circuito. A una trayectoria que no incluye la
misma arista más de una vez se le llama simple.
11. Gráfica Conexa. – Es un grafo en que todos sus vértices están

conectados por un camino (si el grafo es no dirigido) o por un
semicamino (si el grafo es dirigido). Un grafo que no es conexo se
denomina grafo disconexo o inconexo. Los subgrafos conexos máximos
de un grafo no dirigido se llaman componentes o componentes conexos.
Para el caso de los grafos dirigidos, si no se considera el sentido de las
aristas, se habal de componentes debilmente conexo, mientras que si se
considera el sentido, se habla de componentes fuertemente conexo.
12. Árbol. – Es un grafo en el que cualquier par de vértices están
conectados por exactamente un camino, o alternativamente, es un grafo
conexo acíclico. También, un bosque es un grafo disconexo acíclico.
Alternativamente, se puede definir como una unión disjunta de árboles,
es decir, es un grafo disconexo cuyas componentes son árboles.
13. Comenta tus definiciones en función de similitudes y analogías que

encuentres en el mundo real y en otras disciplinas (matemáticas o no).
R = La mayoría de aplicaciones que se tienen a estos conceptos es el diseño
de estructuras y sobre todo se utiliza en programas de diseño como autocad,
Phython, Java, C, etc.
Conclusiones
En esta actividad del foro, se realiza las definiciones de algunos conceptos
que se trata de la Teoría de Gráfos, tales como grafo, vertices, aristas, orden
de grafos, grado de vertices, arboles, trayectorias, caminos, ciclos, grafos
conexos, etc., al final se agrega imágenes para ver de que trata cada
conceptos de teoria de grafos, asi mismo, se escribe algunas aplicaciones que
pueden resolver como un algoritmo de AutoCad. Y con esto, se termina la
actividad.
Bibliografía
Anónimo. (2020). Universidad Nacional de Colombia. Obtenido de 3.
Aplicación: Grafos y dígrafos:
https://ciencias.medellin.unal.edu.co/cursos/algebra-lineal/clases/8-
clases/40-clase-2-
parte3.html#:~:text=Una%20trayectoria%20en%20un%20grafo,v%C3%
A9rtice%20se%20le%20llama%20circuito.
D. Safe, M. (2.o semestre 2018). PDF. Obtenido de Tópicos Fundamentales
en Teoría de Grafos:
https://www.ic.fcen.uba.ar/materias/grafosSafe/Introduccion.pdf
González Gutíerrez, F. J. (Octubre de 2004). PDF. Obtenido de Apuntes de
Matemática Discreta 14. Grafos:
file:///D:/UnADM/Clases%20Universidad/Semestre%202/Matem%C3%
A1ticas%20Discretas/GrafosLeccion14.pdf
Licencia Creative Commons Atribución. (19 de Mayo de 2020). Wikipedia La
Enciclopedia Libre. Obtenido de Grafo completo:
https://es.wikipedia.org/wiki/Grafo_completo
Licencia Creative Commons Atribución. (3 de Junio de 2021). Wikipedia La
Enciclopedia Libre. Obtenido de Grafo dirigido:
https://es.wikipedia.org/wiki/Grafo_dirigido
Enciclopedia Libre. Obtenido de Grafo ciclo:
https://es.wikipedia.org/wiki/Grafo_ciclo
Enciclopedia Libre. Obtenido de Árbol (teoría de grafos):
https://es.wikipedia.org/wiki/%C3%81rbol_(teor%C3%ADa_de_grafos)
Licencia Creative Commons Atribución. (3 de Julio de 2022). Wikipedia La
Enciclopedia Libre. Obtenido de Grafo:
https://es.wikipedia.org/wiki/Grafo
Licencia Creative Commons Atribución. (3 de Julio de 2022). Wikipedia La
Enciclopedia Libre. Obtenido de Grado (teoría de grafos):
https://es.wikipedia.org/wiki/Grado_(teor%C3%ADa_de_grafos)
Enciclopedia Libre. Obtenido de Camino (teoría de grafos):
https://es.wikipedia.org/wiki/Camino_(teor%C3%ADa_de_grafos)
Licencia Creative Commons Atribución Compartir Igual 3.0. (5 de Mayo de
2021). Wikipedia La Enciclopedia Libre. Obtenido de Grafo conexo:
https://es.wikipedia.org/wiki/Grafo_conexo
UnADM. (20 de Enero de 2020). PDF. Obtenido de Unidad 2 "Teoría de
Gráficas y Relaciones":
file:///D:/UnADM/Clases%20Universidad/Semestre%202/Matem%C3%
A1ticas%20Discretas/U2_Contenido.pdf

Mmdi U2 A1 Ulmh

Cargado por

Copyright:

Formatos disponibles

Mmdi U2 A1 Ulmh

Cargado por

Información del documento

Descripción original:

Título original

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

Mmdi U2 A1 Ulmh

Cargado por

Copyright:

Formatos disponibles

Nombre del alumno: Ulises Manzano Hernández

Grupo: MT – MMDI – 2001 – B1 – 003

Materia: Matemáticas Discretas

Carrera: Licenciatura en Matemáticas

Nombre de la Actividad: Actividad 1 “Conceptos Fundamentales de la Teoria

Nombre de la escuela: Universidad Abierta y a Distancia de México

Nombre del profesor: Jose Eduardo García Mendiola

Fecha de entrega: 10 al 16 de Febrero de 2020

2. Digrafo. – Tambien llamado grafo dirigido es un tipo de grafo en el cual

3. Orden de una gráfica. – Se llama asi a su número de vertices, |𝑉|.

5. Grado de un vertice. – es el número de aristas incidentes al vertice. El

6. Grafo Completo. – En teoria de grafos, es un grafo simple donde cada

7. Camino. – Es una sucesión de vértices y aristas dentro de un grafo, que

8. Ciclo. – Es un grafo que consiste en un camino simple cerrado, es decir,

10. Trayectorias. – En un grafo es una secuencia de aristas que

11. Gráfica Conexa. – Es un grafo en que todos sus vértices están

13. Comenta tus definiciones en función de similitudes y analogías que

También podría gustarte