INFO de grafos

Infografía GRAFOS

¿QUE ES UN GRAFO?

Un grafo es un conjunto de objetos llamados vertices o nodos unidos por enlaces llamados aristas o arcos que permiten representar relaciones binarias entre elementos de un conjunto. Un grafo se representa graficamente como un conjunto de puntos(vertices o nodos) unidos por lineas(aristas)

¿Cuáles son características y elementos de un grafo?

• Un grafo (G) es un par ordenado de V y A, donde V es el conjunto de vértices y A es un conjunto de pares de vértices, un vértice puede tener 0 o más aristas las cuales deben unir dos vértices.
• Los grafos representan un conjunto de elementos que no tienen restricción de relación entre ellos lo que significa que no importa el tipo de elemento que lo componga.
• Los grafos están compuestos por: aristas, vértices y los caminos que contenga el grafo.
• la notación para identificar los grafos es la siguiente G = A (V, A).

Un ejemplo es que observando la figura de arriba podemos notar como esta compuesto un grafo. Otro ejemplo de la composición de los grafos es que en estos cada arista debe unir dos vértices y no hay forma de que esto no sea posible ya que es básico de su estructura.

¿Mencionar tipos de grafos?

• Grafo acíclico : Es aquel grafo no contiene ningún ciclo simple.

• Grafo cíclico : Un grafo se dice cíclico si contiene algún ciclo simple.

• Grafo bipartito : Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve que un grafo es bipartito si no hay ciclos de longitud impar.

• Grafo completo : Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo. Además es un grafo simple en el que cada vértice es adyacente a cualquier todo otro vértice.

• Grafo conexo :Decimos que es un grafo conexo, si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo.

Infografía GRAFOS

¿Mencionar tipos de grafos?

• Grafo denso : Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.

• Grafo dirigido: Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista perteneciente al conjunto de aristas E se asocia con dos vértices en forma ordenada.

• Grafo no dirigido : Son aquellos grafos en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas

• Grafo nulo : El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

• Grafo plano : Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de aristas se crucen entre sí.

• Grafo ponderado : Un grafo ponderado es aquel que asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas.

• Grafo regular : Un grafo regular es un grafo cuyos vértices tienen el mismo grado.

• Grafo simple :Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un multígrafo.

• Grafo no Simple: Grafo no dirigido que tiene lados paralelos y lazos.

• Grafo trivial: Un grafo trivial es aquel grafo vacío con un único vértice.

• Grafo vacío : Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.

¿ A que se refieren las valencias de un grafo?

Valencia: Es el número de lados que salen o entran a un vértice. Las veces que una arisca toca un vértice. ejemplo 1 ejemplo 2

Infografía GRAFOS

¿Qué es una matriz de incidencia y de adyacencia?

Matriz de incidencia La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.

Matriz de adyacencia La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice y el número de unos que aparecen en una determinada columna es igual al grado de entrada del correspondiente vértice.