TAREA 3: GRAFOS Y ARBOLES
Enviado por Jimmy Hermida • 12 de Diciembre de 2020 • Ensayo • 986 Palabras (4 Páginas) • 1.764 Visitas
TAREA 3: GRAFOS Y ARBOLES
PRESENTADO POR:
JIMMY ALEXANDER GUERRA HERMIDA
CÓDIGO: 1007862079
TUTOR:
DANIEL FERNEY LUGO
CÓDIGO CURSO:
204041_81
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
MATEMÁTICAS DISCRETAS
INGENIERÍA DE SISTEMAS
FECHA OCTUBRE 2020
UDR PUERTO ASIS PUTUMAYO
INTRODUCCION
Para esta actividad cada estudiante debe elegir que ejercicio va a resolver yo elegí el ejercicio estudiante E resolver cada uno del puntos los cuales sus temas son grafos y árboles.
OBJETIVOS
- Leer la unidad 3 para comprender la realización del trabajo
- Realizar los ejercicios y tener claridad con el tema grafos
- Realizar los ejercicios y tener claridad con el tema arboles
- Por ultimo recordase estos temas y nunca olvidarlos
ESTUDIANTE “E”
- Con el siguiente grafo:[pic 1]
[pic 2]
[pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10]
[pic 11]
[pic 12][pic 13][pic 14][pic 15]
- Describa formalmente el grafo
El grafo G5 es un grafo básico y está formado por el conjunto de elementos (V, U, W, X) el cual llamaremos vértices los cuales están intersectados por medio de cinco vértices quienes se describen en parejas ordenadas y conformando el subconjunto del conjunto G5.
- Halle el grado y paridad de cada vértice
[pic 16]
Grado de los vértices
[pic 17]
[pic 18]
- Verifique si cumple que la suma de los grados de los vértices de un grafo es igual a dos veces el número de aristas
Si se cumple ya que la suma de los grados de los vértices es 10 y corresponde al doble del número de aristas, las cuales son 5
No. Aristas = 5
Suma de gados vértices = 10
- a) Responda lo siguiente: ¿Cuál es la diferencia entre dígrafo, grafo y multígrafo?
El Dígrafo:” Un grafo dirigido o dígrafo es un tipo de grafo en el cual las aristas tienen un sentido definido, a diferencia del grafo no dirigido, en el cual las aristas son relaciones simétricas y no apuntan en ningún sentido
El Grafo: es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto
El Multígrafo: es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. ... E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.
- Determine gráficamente si el multígrafo G5= {V, E}, es o no es grafo, donde
V = {a, b, c, d} y E = {(a, b), (a, c), (a, d), (b, c), (c, c)}
[pic 19]
[pic 20][pic 21][pic 22][pic 23][pic 24]
[pic 25][pic 26][pic 27][pic 28][pic 29]
[pic 30]
[pic 31][pic 32]
RTA: No es un grafo porque no esta completo y no todas las aristas están uniendo todas las pares posibles de vértices.
- Realice el grafo a partir de la información dada en la matriz de adyacencia:[pic 33][pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41][pic 42]
a | b | c | d | e | |
a | 1 | 0 | 1 | 1 | 1 |
b | 0 | 1 | 1 | 1 | 0 |
c | 1 | 0 | 0 | 0 | 1 |
d | 1 | 1 | 0 | 0 | 0 |
e | 0 | 0 | 0 | 0 | 1 |
[pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51]
- Para el siguiente árbol
[pic 52]
Determine…
- Nodos hoja, nodos rama.
RTA: Nodos ramas: “C, E, J” Nodos Hoja: “A, G, H, I, N, M, K”
- La raíz del árbol
RTA: La raíz del árbol es “D”
...