Grafos.

GRAFOS (ARBOLES).

Es un grafo simple en el cual exisiste un unica camino entre cada par de vertices.
tambien podemos decir que es un grafo no dirigido conexo que no contiene circuitos, es decir, no existe dos o mas paseo sobre un par de vertices.

Estructura de datos dinamica, jerarquica y no lineal.

-Dinamica: su tamaño cambia durante el punto de ejecución.

-Jerárquica: sus nodos se organizan por niveles, en la que los nodos de niveles superiores se conocen como ancestros o padres y los nodos de niveles inferiores se llaman descendientes o hijos.

- No lineal: Existe mas de una manera de recorrer a un arbol.

PROPIEDADES.

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

TIPOS

Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:

• Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo.
• Grafo vacío: aquel que no tiene aristas.
• Grafo trivial: aquel que tiene un vértice y ninguna arista.
• Grafo simple: aquel que no posee bucles ni aristas paralelas. Consultar variantes en esta definición.
• Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Consultar variantes en esta definición.
• Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
• Grafo bipartito: sea ${\displaystyle (W,X)}$ una partición del conjunto de vértices ${\displaystyle V}$, es aquel donde cada arista tiene un vértice en ${\displaystyle W}$ y otro en ${\displaystyle X}$.
• Grafo bipartito completo: sea ${\displaystyle (W,X)}$ una partición del conjunto de vértices ${\displaystyle V}$, es aquel donde cada vértice en ${\displaystyle W}$ es adyacente sólo a cada vértice en ${\displaystyle X}$, y viceversa.
• Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
• Árbol: grafo conexo sin ciclos.
• Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).
• Grafo perfecto aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.