Grafo

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 {v₁, v₂, ..., v_k,...} y A es el conjunto de pares {v_i, v_j}, tales que v_i y v_j 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 (v_i, v_j) ó <v_i, v_j> 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|.

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: K_n es el grafo completo de orden n.
• Grafo bipartido: Es el grafo tal que su conjunto V de nodos puede separarse en V₁ y V₂ sin coincidencias entre ambos, donde cada arista suya tiene un extremo en V₁ y otro en V₂.
• Grafo bipartido completo: Es un grafo bipartido tal que cada nodo de V₁ est unido a todos los de V₂.
• Grafo plano: Es el grafo que puede representarse en un plano sin que ninguna arista (o arco) se cruce con otra.

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.