TEORÍA DE GRAFOS

1. CONCEPTO DE GRADO Se llama grado de v al número de aristas incidentes en v. si la arista es un bucle en v, contribuye con dos unidades al valor del grado

1.1. GRADO ENTRANTE DE UN VERTICE Es el número de aristas que llegan al vértice

1.2. Grado saliente de un vértice Corresponde al número de aristas que salen del vértice

1.3. Grado de un vértice Al número de aristas que lo tiene como extremo (cada bucle lo cuenta dos veces). Se designa por d(v), y corresponde al número de aristas incidentes sobre el vértice. (un vértice aislado tiene grado cero)

2. COMPONENTES DE UN GRAFO (VÉRTICES, ARISTAS, LAZOS Y VALENCIA)

2.1. ARISTAS: Una arista es una relacion entre dos vertices de un grafo

2.1.1. ARISTAS ADYACENTES: Estas son dos aristas que se dirigen en el mismo vértice y se juntan en él.

2.1.2. ARISTAS PARALELAS: Estas estas son dos aristas si el vértice inicial y el final son uno mismo

2.2. CRUCE: Son dos aristas que cruzan en un punto.

2.3. GRADO O VALENCIA DE UN VÉRTICE: Es el número de aristas que inciden sobre un vértice.

2.4. LAZO: Es una arista cuales extremos inciden sobre el mismo vértice.

2.5. VERTICE: Son puntos o nudos con los que están conformado los grafos. Llamaremos grado de una vértice, al número de aristas de las que es extremo, se le dice vértice par o impar según sea su grado.

2.5.1. VERTICE ADYACENTE: Los vértices son adyacentes si están unidos mediante una arista. VERTICE AISLADO: Es un vértice de grado cero. VERTICE TERMNAL: Es un vértice de grado 1

3. CONCEPTO DE GRAFO: Es una pareja de conjuntos (V,E), donde: V es distinto de vacio, E es un conjunto de pares de elementos deV

3.1. GRAFO DIRIGIDO Un grafo dirigido es aquel que tiene todas sus aristas dirigidas; es decir, un dígrafo esta asociado a un par ordenado.

3.2. GRAFO NO DIRIGIDO. Un grafo no dirigido, consta de un conjunto de vértices y un conjunto E de aristas tal que cada arista e E E queda asociada a un par no ordenado de vértices

3.3. GRAFO MIXTO. Es aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas, un grafo no dirigido puede dibujarse con aristas dirigidas haciendo que cada lado les corresponda aristas invertidas.

4. CAMINOS, CADENAS Y CICLOS

4.1. CADENA: A toda sucesión finita alterna de vértices y aristas.

4.2. CADENA CERRADA: toda cadena en la que los vértices inicial y final coinciden

4.3. CAMINO: A toda cadena en a que no se repite ni vértices ni aristas (resp. Arcos)

4.4. CICLO: Cadena en la que no se repite ninguna arista

4.5. LONGITUD DE CADENA: Numero de aristas (resp. Arcos) que la forman