Saltar a: navegación, buscar

Grafo

Grafo
Información sobre la plantilla
K333.png
Concepto:G=<V,A>, donde V es el conjunto de nodos y A es el conjunto de aristas dadas por pares <vi,vj> para vi y vj nodos de V

Grafo. Abstracción matemática definida por la relación G=<V,A> donde V es el conjunto de nodos o vértices y A es el conjunto de pares que definen los arcos o aristas que unen pares de vértices o lazos si unen a un vértice consigo mismo.

Antecedentes

Fue Euler el primero en referirse a los grafos y a hacer uso de una suerte de teoría en la publicación "Solutio problematis ad geometriam situs pertinentis" de 1736 para dar solución al Problema de los Puentes de Königsberg (actualmente Kaliningrado), concluyendo que era imposible recorrer todas las riveras, pasando por todos los puentes, sin repetir ninguno y de ahí se constituyó el concepto también de Grafo euleriano.

Definiciones.

Se entiende por grafo G al par <V,A> donde V es el conjunto de nodos o vértices {v1, v2, ..., vk,...} y A es el conjunto de pares {vi, vj}, tales que vi y vj pertenecen a A, que definen las aristas que unen pares de vértices o lazos si unen a un vértice consigo mismo.

Grafo no dirigido o grafo no orientado coincide en este caso con la definición de grafo.

Grafo orientado.

La definición de grafo orientado y la de grafo distan solo en un aspecto que en lugar de aristas, tiene arcos que se representan según los autores como (vi, vj) ó <vi, vj> y a diferencia de la notación conjuntual son ordenados, lo cual implica que la relación se establece solo en el sentido en que aparecen los nodos en el arco.

Desde el punto de vista gráfico los arcos tienen orientación indicada con una flecha al extremo del nodo destino, del lado saliente no tiene nada.

Orden.

Se entiende por orden del grafo G=<V,A>, definido como |G|, al resultado |G|=|V|.

Camino.

Dentro de un grafo G=<V,A> un camino entre los nodos vi y vj es una secuencia ordenada de nodos vi,vk1,vk2,...,vj que indica que entre vi y vk1 hay una arista, que entre vk1 y vk2 hay una arista y así sucesivamente hasta llegar a vj.

Ciclo.

Un ciclo es un camino que inicia y termina en el mismo nodo.

Matriz de adyacencia.

Dado un grafo G=<V,A> de orden N al mismo se le asocia una matriz de adyacencia M cuadrada NxNdonde cada fila y columna se asocia a un cada nodo específico y las celdas contienen la cantidad de aristas que hay entre el nodo de la fila y el nodo al que identifica la columna.

En el caso de los grafos no orientado la matriz de adyacencia es simétrica pues las aristas identifican flujo bidireccional. En los dígrafos los arcos no son bidireccionales por tanto la matriz no tiene por qué serlo.

La matriz también permite representar los grafos pues contiene tanto la información de los nodos como acerca de las aristas entre ellos, haciéndola ideal para representaciones computacionales.

Grafos notables.

Dentro de los grafos existe una gran colección de grafos llamados notables.

  • Grafo nulo: Es el grafo sin nodos.
  • Grafo vacío: Es el grafo que no tiene aristas.
  • Grafo unitario o trivial: Tiene un solo nodo sin lazos.
  • Grafo simple: Es el grafo sin lazos.
  • Grafo conexo: Es el grafo donde entre cualquier par de vértices existe una forma de ir entre ellos.
  • Grafo completo: Grafo donde existe una arista (o arco si es dirigido) entre cualquier par de vertices distintos.
  • Kn: Es el grafo completo simple de orden n.
  • Grafo bipartido: Es el grafo tal que su conjunto V de nodos puede separarse en V1 y V2 sin coincidencias entre ambos, donde cada arista suya tiene un extremo en V1 y otro en V2.
  • Grafo bipartido completo: Es un grafo bipartido tal que cada nodo de V1 est unido a todos los de V2.
  • Grafo plano: Es el grafo que puede representarse en un plano sin que ninguna arista (o arco) se cruce con otra.
  • Árbol: Grafo conexo sin ciclos.
  • Grafo euleriano: Grafo que tiene caminos eulerianos.

Veáse también.

Fuentes.

  1. |Grafo en Wikipedia.
  2. K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988.
Se sugiere la categoría Matemática discreta o Teoría de conjuntos.