Demuestre que el grafo simple no dirigido definido por las siguientes aristas en formato (inicio. Final) es plano (1,2), (1,3), (1,4), (2,4), (2,6), (3,5), (3,6), (4,5), (5,6).
Luego ejecuta paso por paso una búsqueda de profundidad (DFS) que imprime los vértices en postorden, iniciando el recorrido en el vértice con etiqueta 3 y visitando siempre primero aquel vecino no visitado que tiene el menor etiqueta.
El gráfo quedaria de esta manera, el cual es plano ya que ninguna de sus Aristas se cruzan o intersecan entre si.
El diámetro del grafo es:2
El grado de un vértice ,es el numero de aristas adyacentes al vértice, por lo tanto el grado de el grafo se calculara sumando el grado de cada vértice y dividiendo entre el numero de vértice.
Vértice 1.- es de grado 3 (por que tiene 3 aristas adyacentes al vertice)
Vértice 2.- es de grado 3
Vértice 3.- es de grado 3
Vértice 4.- es de grado 3
Vértice 5.- es de grado 3
Vértice 6.- es de grado 3
Primero sumamos los grados de cada vértice, que nos da un total de 18,
Después dividimos entre el numero de vértices, que en este caso son 6.
Asi que 18/6 = 3 por lo tanto el grado promedio es 3.
Los vértices en postorden son: (6,5,4,2,1,3)
Muy buena la explicacion con eso resolvi la duda que tenia de que era lo que definia el grado del vertice (las aristas adyacentes)en este caso para todas son 3 gracias..
ResponderEliminar