Prueba - Aplicaciones e Interpretación Nivel Sup. | Page 34

∑M muestra el número de caminos de longitud menores o iguales a p r = 1
Su Prueba de Práctica – AI NS para las Matemáticas del PD del IB
� Matriz de adyacencia M de un grafo con n vértices : 1 . n× n: Orden de M 2 . La entrada m ij
= 1 si hay una arista conectando el vértice i y el vértice j ,
3 . 4 . de otra forma m ij
= 0 p
M muestra el número de caminos de longitud p en el grafo p r
∑M muestra el número de caminos de longitud menores o iguales a p r = 1
en el grafo 5 . La suma de la columna de la matriz de transición de un grafo dirigido debe ser igual a 1
�
Algoritmos para encontrar árboles generadores minimales :
1 .
Algoritmo de Kruskal
2 .
Algoritmo de Prim
�
Senderos y circuitos Eulerianos :
1 .
Sendero : Una secuencia de aristas que pasan por cualquier arista al menos
una vez
2 .
Circuito : A sendero que comienza en el que el vértice del comienzo es en
vértice del final
3 .
Sendero Euleriano : Un sendero que pasa por todas las aristas de un grafo
4 .
Circuito Euleriano : Un circuito que pasa por todas las aristas del grafo
5 .
Un sendero Euleriano existe si hay dos y solo dos vértices de grado impar
6 .
Un circuito Euleriano existe si todos los vértices son de grado par
7 .
El problema del cartero chino puede ser usado para encontrar la ruta del
peso mínimo que cubre todas las aristas de un grafo
� Caminos y ciclos hamiltonianos : 1 . Grafo completo : Un grafo en el que existe una arista para cualquier par de dos vértices 2 . Camino Hamiltoniano : Un camino que pasa por todos los vértices de un grafo 3 . Ciclo Hamiltoniano : Un ciclo que pasa por todos los vértices de un grafo
22
SE Production Limited