GRAFOS NO ORIENTADOS

GRAFOS NO ORIENTADOS
MATRICES DE ADYACENCIA DE VERTICES
MATRICES DE INCIDENCIA DE ARISTAS
GRAFO CONEXO
COMPONENTE CONEXA
TEOREMA
DEMOSTRACIÓN
COROLORIO
MATRIZ DE CONECCION
ANALISIS DE CONECCIDADGRAFOS NO ORIENTADOS
UN GRAFO NO ORIENTADOS ESTA COMPUESTO POR LA TERNA G=(A,V,@) DONDE A LOS ELEMENTOS DE A SON LLAMADOS ARISTAS DE G LOS ELEMENTOS DE V SON LLAMADOS VERTICES O NODOS DE G Y @ ES UNAFUNCION DE INDIDENCIA QUE ASIGNA A CADA ARISTA UN PAR NO ORDENADO DE VERTICES LLAMADOS SUS EXTREMOS


MATRIZ DE ADYACENCIA DE VERTICES DE GRAFOS NO ORIENTADOS
ES UNA MATRIZ SIMETRICA Y CUADRADA.DONDE LA SUMA DE LOS ELEMENTOS DISTINTOS DE CERA ES IGUAL AL DOBLE DEL NUMERO DE ARISTAS CONTANDO DOBLE A LA DIAGONAL PRINCIPAL




TEOREMA DE MATRIZ ADYACENDE DE VERTICES
Si M es un matriz de adyacenciade un grafo G, el elemento Mij=/=0, de la matriz Msignma, sigma perteneciente a los naturalez, este indica la existencia de por lo menos un camino de longitud sigma de vi a vj.
Corolario
En un grafoexiste por lo menos un camino de longitud sigma, si Msigma distinta de la matriz nula,
Matriz de incidencia de aritas
Es una matriz rectangular Mnxr donde n es igual al modulo de V y r es igual almodulo de A.


TEOREAMA
En la matriz de incidencia de aritas, cada columna presenta exactamente 2 unos, correspondientes a las filas de los vertices que son extremos de dichas aritas, y cada filapresenta tantos uno como el grado del vertice correspondiente a dicha fila.

Grafos no orientados conexos
Cadena: es una suceción finita de aritas
Grafo no orientado conexo: en un grafo G, dados cualesquierados vertices v y w en G, existe una cadena que va de v a w.
definimos la siguiente relación en el grafo (V,A,@): EL VERTICE VJ ES ALCANZABLE DESDE VI , SI EXISTE UNA CADENA QUE UNE VI A VJ
Componenteconexa: es el subgrafo generado por vn y todos los vertices conectados a vn a travez de una cadena.


TEOERAMA: la relación " es alcanzable desde" definida en el conjunto de vértices v de un grafo...