Definiciones Basicas

DEFINICIONES BÁSICAS

GRAFO DIRIGIDO O DÍGRAFO

Es un tipo de grafo en el cual las aristas tienen una dirección definida, a diferencia del grafo generalizado,

 en el cual la dirección puede estar especificada o no.

Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos

donde:

un conjunto no vacío de objetos simples llamados vértices o nodos.

es un conjunto de pares ordenados de elementos de   denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.

GRAFOS NO DIRIGIDOS

El grado de un vértice es el número de aristas incidentes con él, cada bucle se cuenta dos veces:

- Denotaremos el grado de un vértice por dG(Vértice).

- Denotaremos el conjunto de vértices adyacentes por Γ(Vértice).

Arista Puente

En teoría de grafos, un puente, arista de corte o istmo es una arista que al eliminarse de un grafo incrementa el número de componentes conexos de éste. Equivalentemente, una arista es un puente si y sólo si no está contenido en ningún ciclo.

Un grafo con 6 aristas de corte (marcadas en rojo)

Lazo

Es una arista cuyos extremos inciden sobre el mismo vértice

                                 

Grado

El grado de un vértice es el  número  de aristas que se encuentran en ese vértice. En un  sentido  más formal El grado de un vértice V en un grafo G, se escribe grd (v), Es decir es  igual al número de aristas en G que contienen a v; es decir, que inciden sobre v.

En  el  caso  de digrafos se distingue entre el grado entrada y el grado salida. EI primero define la cantidad de arcos en los que el nodo  es  el destino y el segundo es la cantidad de arcos donde es el origen.

Vértice Aislado:

Es un vértice de grado cero:  

Vértices adyacentes

Dos vértices son adyacentes si comparten una sola arista.

Trayectoria

Una trayectoria es una sucesión de vértices con la propiedad de que cada vértice es adyacente al siguiente y tal que en  la correspondiente  sucesión  de aristas; todas las aristas son distintas. Es decir que un vértice si puede aparecer en una Trayectoria más de una vez.

Camino

Se llama camino a una secuencia de aristas donde cada par de aristas consecutivas son ambas incidentes con un  mismo  nodo.  Los  nodos  no  necesariamente  comunes  de  la primera y de las últimas aristas se Llaman extremos del camino, mientras que los comunes se llaman intermedios.

 CICLO o CIRCUTO

Un circuito es una trayectoria que inicia  y termina en el mismo vértice. En Teoría

de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un

polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún

vértice a excepción del primero que aparece dos veces como principio y fin del

camino.

Grafo conexo

Un grafo es conexo si cualesquiera dos de sus vértices se pueden unir por una trayectoria. Si una gráfica no es conexa, se dice que es disconexa.

Un grafo G es conexo si existe un camino entre dos de sus vértices.

Grafica disconexa

Una gráfica disconexa esté formada de varios pedazos, cada uno de los  cuales es una gráfica conexa. A los pedazos se les llama componentes  de la gráfica.