APLICACIONES GRAFOS

CONCEPTOS

que es un grafo? conjunto de nodos o vertices unidos por arcos o aristas

ADYACENCIA

dos nodos son adyacentes si el grafo contiene una arista que los une, del mismo modo dos aristas son adyacentes si posen el mismo nodo en comun

SUB-GRAFO

Es un grafo cuyos vértices y aristas pertenecen  a V(G) y E(G)respectivamente

LAZO

es una arista que tiene origen como destino nodo v  y contribuye de manera doble al grado del nodo v

GRADO DE VÉRTICE


Numero de aristas de un grafo que inciden en v . los vértices de grado 0 reciben el nombre de vértices aislados , mientras los de grado 1 se denominan vértices extremo o terminal.

ejemplo

representaciones con grafos

• red computadoras
• conexiones de vuelo aerolínea
• carreteras
• circuitos electrónicos
• representacion de un  mapa

IMPORTANCIA DE ESTUDIAR LOS GRAFOS

• permiten estudiar interrelaciones entre elementos que interactuan unos con otros.
•  Dado un escenario donde ciertos objetos  se relacionan , se pueden modelar el grafo y luego aplicar algoritmos solucionando diversos problemas

GRAFOS PARTICULARES

grafo nulo:  no tiene vértice ni aristas

grafo vació: no tiene aristas

grafo trivial; Tiene un vértice y ninguna arista

                                          .

Grafo simple: no poseen bucles ni aristas

Multigrafo:

es un grafo que esta facultado para tener aristas multiples, es decir aristas que se relacionan con los mismos nodos

grafo completo:

grafo simple en el que cada par de vertices estan  unidos por una arista, es decir, contiene todas las posibles ristas.

Grafo bipartito:

Sea (W,X) una particion del conjunto de vertices V, es aquel donde cada aristaa tiene un vertice en W y otro en X

Grafo Bipartito completo:

sea (W,X) una particion del conjunto de vertices V es aquel donde en cada vertice de W  es adyacente solo a cada vertice X, y viceversa

grafo plano:

Aquel que puede ser dibujado en el plano cartesiano sin cruce ni aristas

Arbol

grafo conexos sin ciclos.

grafo rueda

 grafo con n vértices que se forma conectando un unico vertice a todos los vértices de un ciclo
(n-1)

grafo perfecto

Aquel que cada numero cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo