Libros

Solo disponible en BuenasTareas
  • Páginas : 21 (5159 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de diciembre de 2010
Leer documento completo
Vista previa del texto
1

2

´ MATEMATICA DISCRETA Transparencias curso 2009/2010 Contenido ´ MATEMATICA DISCRETA Bloque 1 ´ INTRODUCCION A LA TEOR´ DE IA GRAFOS Bloque 1. Introducci´n a la teor´ de grafos. o ıa Lecci´n 1. Grafos: fundamentos. o Lecci´n 2. Accesibilidad y Conectividad. o ´ Lecci´n 3. Arboles. o Lecci´n 4. Grafos Ponderados. o Bloque 2. Los Enteros. Lecci´n 1. Los n´meros enteros. o u Lecci´n 2.Congruencias. Aritm´tica modular. o e Transparencias

Lecci´n o Lecci´n o Lecci´n o Lecci´n o

1. 2. 3. 4.

Grafos: fundamentos. Accesibilidad y Conectividad. ´ Arboles. Grafos Ponderados.

3

Matem´tica Discreta a

Grafos: Fundamentos

4

Matem´tica Discreta a

Grafos: Fundamentos

1. DEFINICION Y CONCEPTOS BASICOS Definiciones:

Lecci´n 1. o
1. Un grafo no dirigido G es un par(V, A), en el que V es un conjunto cuyos elementos llamaremos v´rtices, y A una familia de pares no e ordenados de v´rtices, que llamaremos aristas. e

GRAFOS: FUNDAMENTOS

1. 2. 3. 4. 5.

Definici´n y conceptos b´sicos. o a Tipos particulares de grafos. Grado de un v´rtice. e Caminos y conexi´n. o Representaci´n matricial. o

2. Un grafo dirigido G es un par (V, A), en el que V es unconjunto cuyos elementos llamaremos v´rtices, y A una familia de pares ordenados de e v´rtices, que llamaremos arcos. e

3. Llamamos grafo no dirigido asociado a un grafo dirigido, a un grafo con el mismo conjunto de v´rtices y en el que se han ignorado las e direcciones de los arcos.

5

Matem´tica Discreta a

Grafos: Fundamentos

6

Matem´tica Discreta a

Grafos: Fundamentos

2.TIPOS PARTICULARES DE GRAFOS. Definiciones: 1. Un grafo simple es un grafo sin bucles en el que no hay dos aristas que unan el mismo par de v´rtices. Si el grafo es dirigido diremos e que es simple si no tiene bucles y no hay dos arcos uniendo el mismo par de v´rtices y con e la misma direcci´n. Si un grafo no es simple se o llama multigrafo.

4. Un grafo mixto es aquel que contiene tanto arcos comoaristas.

5. Los extremos de una arista (arco) se dice que son incidentes con la arista (arco).

6. Dos v´rtices incidentes con una misma arista e (arco) se dicen adyacentes.

7. Un bucle es una arista (o arco) cuyos extremos son el mismo v´rtice. e

2. Un grafo no dirigido (dirigido) se dice que es completo si hay al menos una arista (arco) uniendo cada par de v´rtices distintos. Denomienaremos por Kn al grafo completo no dirigido y simple.

3. Un grafo no dirigido diremos que es bipartido si existe una partici´n {X, Y } del conjunto o de v´rtices de forma que toda arista tiene un e extremo en X y otro en Y . Un grafo dirigido es bipartido si lo es su grafo no dirigido asociado.

7

Matem´tica Discreta a

Grafos: Fundamentos

8

Matem´tica Discreta a

Grafos:Fundamentos

´ 3. GRADO DE UN VERTICE Definiciones: 1. Llamamos grado de un v´rtice v en un grae fo no dirigido G al n´mero de aristas incidentes u con ´l. Cada bucle se cuenta dos veces. Se dee notar´ por dG(v). a Designamos por Γ(v) al conjunto de v´rtices ade yacentes a v.

4. Diremos que un grafo bipartido es completo si cada v´rtice de X esta unido con cada e v´rtice de Y . e

5. Sean G = (V,A) y H = (V , A ) dos grafos. H es subgrafo de G si V ⊆ V y A ⊆ A.

6. Diremos que un subgrafo H de un grafo G es generador si sus conjuntos de v´rtices son e iguales.

2. Sea G un grafo dirigido. Llamaremos grado de salida de un v´rtice v y lo denotaremos por e ds(v) al n´mero de arcos salientes de v. Llamau remos grado de entrada de un v´rtice v y lo e denotaremos por de(v) al n´mero dearcos enu trantes en v. Se llamar´ grado de un v´rtice a a e la suma de estos dos grados. An´logamente se puede definir Γ(v) y Γ−1(v). a

9

Matem´tica Discreta a

Grafos: Fundamentos

10

Matem´tica Discreta a

Grafos: Fundamentos

4. CAMINOS Y CONEXION Definiciones: Sea G un grafo no dirigido: Teorema 1. Sea G = (V, A) un grafo, entonces dG(v) = 2card(A)
v∈V

1. Una cadena es una...
tracking img