Hola

1

Grafos: Primeras definiciones

Definici´n 1.1 Un grafo G se define como un par o (V, E), donde V es un conjunto cuyos elementos son denominados v´rtices o nodos y E es un subconjunto e de pares no ordenados de v´rtices y que reciben el e nombre de aristas o arcos. Si V = {v1, · · · , vn}, los elementos de E se representa de la forma {vi, vj }, donde i = j. Los elementos de una arista o arcose denominan extremos de dicha arista. Dos v´rtices vi y vj se dicen adyacentes si e {vi, vj } ∈ E.

Un grafo G = (V, E) se dice finito si V es un conjunto finito.

Definici´n 1.2 Un multigrafo G se define, al igual o que un grafo, por un par (V, E) donde V es el conjunto de v´rtices o nodos y E el de aristas o arcos, e pero con la salvedad de que en este caso el conjunto E puede contener mas deuna arista cuyos extremos son los mismos, as´ como aristas del tipo {vi, vi} deı nominadas lazos.
1

Dado G un grafo es posible hacerle corresponder una matriz. Dicha matriz M = (mij ) viene definida por mij = 1 en caso de que los v´rtices vi y vj sean adye acentes y 0 en caso contrario. Es claro pues que la matriz de adyacencias de un grafo es siempre una matriz sim´trica. e

Definici´n 1.3 SeaG = (V, E) un grafo. Un subo grafo de G es un par (V , E ) donde V ⊆ V y E ⊆ E y para cada elemento de E , sus extremos est´n en a V . Si E contiene todos los elementos de E cuyos extremos est´n en V , entonces se llama subgrafo gena erado por V .

Definici´n 1.4 Sea G = (V, E) un grafo. Un camino o en el grafo G es una sucesi´n en la que aparecen o de forma alternativa elementos de V y de E dela forma v0, e1, v1, e2, v2, · · · , vn−1envn con vi ∈ V para i = 0, · · · , n y ej ∈ E para j = 1, · · · , n. y donde vi−1 es adyacente con vi mediante la arista ei. El n´mero u de arcos que componen un camino se denomina longitud de dicho camino.
2

Definici´n 1.5 Sea G un grafo y sea o v0, e1, v1, e2, v2, · · · , vn−1envn un camino en G. Se dice que dicho camino es un camino cerrado si v0 =vn. En caso contrario se denomina camino abierto que conecta v0 con vn.

Definici´n 1.6 Sea G un grafo y sea o v0, e1, v1, e2, v2, · · · , vn−1envn un camino en G. Se dice que dicho camino es un camino simple si todos los arcos que aparecen en el mismo son distintos. Se dice que un camino es una trayectoria si todos los v´rtices que aparecen son dise tintos. De este modo, toda trayectoria es uncamino simple.

Se dice que tal camino es un ciclo cuando todos los v´rtices que aparecen en el mismo son distintos salvo e v0 = vn. Un ciclo de longitud n se denomina n-ciclo.
3

Definici´n 1.7 Se dice que G es un grafo conexo si o para cualquier par de v´rtices de G existe una trayece toria entre ellos. Un subgrafo de un grafo no conexo G se dice que es una componente conexa de G si es, ens´ mismo, un grafo conexo. ı

Definici´n 1.8 Sea G un grafo. La distancia entre o dos v´rtices de G es el m´nimo de las longitudes de toe ı das las trayectorias entre dichos v´rtices. El m´ximo e a de las distancias entre todos los v´rtices de G se dee nomina di´metro de G. a

Proposici´n 1.9 Sea G un grafo y u y v elementos o de V . Existe un camino entre u y v si y s´lo si existe o unatrayectoria entre u y v.

Teorema 1.10 Sea M la matriz de un grafo G. Entonces el elemento mij de la matriz M n proporciona el n´mero de caminos de longitud n entre el v´rtice u e vi y el vj .
4

2

Grado de un v´rtice e

Definici´n 2.1 Sea G un grafo y v ∈ V . Se define o el grado de v como el n´mero de aristas de las cuales u es extremo v.

Proposici´n 2.2 La suma de los grados de un grafo o Ges igual al doble de los elementos de E.

Definici´n 2.3 Un grafo G se dice que es un grafo o de Euler si existe un camino cerrado en G de manera que contiene a todas las aristas de G exactamente una sola vez.

Teorema 2.4 Un grafo G es de Euler si y s´lo si G o es conexo y el grado de todos sus v´rtices es par. e

Definici´n 2.5 Un grafo conexo G se dice recorrio ble si existe un camino...