Gregorio Hernández Peñalver Departamento de Matemática Aplicada, Facultad de Informática, UPM

Matemática Discreta

TEMA 4 GRAFOS
NOCIONES BÁSICAS
Un grafo es un par G=(V,A), donde V es un conjunto finito no vacío (a cuyos elementos llamaremos vértices) y A es una familia finita de pares no ordenados de vértices de V (a cuyos elementos llamaremos aristas o arcos). Un grafo simple es un par G=(V,A) donde V es un conjunto finito no vacío y A es un conjunto finito de pares no ordenados de vértices distintos de V. Si a={u,v} es una arista de G escribiremos sólo a=uv, y diremos que a une los vértices u y v o que u y v son extremos de a. Una arista a=uu se llama bucle. Una arista que aparece repetida en A se llama arista múltiple. (En …ver más…

Designaremos por k(G) al nº de componentes conexas del grafo G Un vértice v se llama vértice-corte (o punto de articulación) de G si el grafo G-{v} tiene más componentes conexas que G. Una arista a de un grafo G se llama puente si G-{a} tiene más componentes conexas que G. Los bloques de un grafo G son los subgrafos de G sin vértices-corte y maximales con respecto a esta propiedad. Propiedades: 1) Una arista e de un grafo conexo es un puente de G ⇔ la arista e no pertenece a ningún ciclo de G. 2) Si dos bloques comparten un vértice, éste debe ser un vértice-corte

DIGRAFOS Un digrafo o grafo dirigido es un par D=(V,A) donde V es un conjunto no vacío (a cuyos elementos llamaremos vértices) y A es una familia finita de pares ordenados de vértices de V (a cuyos elementos llamaremos aristas o arcos). Un digrafo simple es un par D=(V,A) donde V es un conjunto no vacío y A es un conjunto finito de pares ordenados de vértices distintos de V. Si a=(u,v) es un arco escribiremos a=uv, y diremos que u es extremo inicial de a y que v es extremo final de a. Se llama grado de entrada de un vértice v al número de arcos que lo tienen como extremo final y se llama grado de salida de v al número de arcos que lo tienen como extremo inicial. La matriz de adyacencia de un digrafo D con n vértices {v1,...,vn} es una matriz nxn, M(D)=(aij) donde es el número de arcos que tienen a vi como extremo inicial y a vj como extremo final. Un camino dirigido en un digrafo es una sucesión de