18
Teoría de Grafos
� Terminología de grafos : Vértice : Un punto en un grafo Arista : Arco que conecta vértices Camino : Una secuencia de aristas Cruce : Una secuencia de aristas que pasan a través de cualquier vértice y cualquier arista al menos una vez Grado de un vértice : Número de aristas conectando los vértices Grafo conectado : Un grafo que existe al menos un camino entre cualesquiera dos vértices Grafos no conectados : Un grafo que existe al menos dos vértices que no hay camino entre ellos Subgrafo de un grafo : Una colección de algunas aristas y vértices del grafo original Círculo : Una arista que comienza y termina en el mismo vértice Grafo simple : Un grafo que no tiene círculos y no múltiples aristas conectando los mismos pares de vértices Grafo múltiple : Un grafo que tiene múltiples aristas conectando al menos un par de vértices Ciclo : Un cruce en el que el vértice de comienzo es el vértice del final Árbol : Un grafo conectado sin ciclos Árbol de expansión : Un árbol que conecta todos los vértices en el grafo
� Grafos dirigidos : 1 . Grafos dirigidos : Un grafo en el que todas las aristas tienen un sentido asignado 2 . Grado de entrada : Número de aristas conectando y apuntando hacia el vértice 3 . Grado de salida : de aristas conectando y apuntando hacia afuera del vértice
21 www . seprodstore . com