Términos claves de la teoría de grafos

A continuación en este pequeño resumen introduciremos parte de la terminología básica de teoría de grafos.

Un grafo es una pareja G = (V, E), donde V es un conjunto de puntos, llamados vértices, y mientras que E es un conjunto de pares de vértices, llamadas aristas. Un vértice o nodo es la unidad fundamental de la que están formados los grafos mientras que una arista corresponde a una relación entre dos vértices de un grafo y por eso un grafo permite representar relaciones binarias entre elementos de un conjunto y son objeto de estudio de la teoría de grafos. Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.

Entre sus propiedades tenemos que el número de un vértice de un grafo G, es el orden del grafo, el número de una arista de un grafo G, su tamaño y si 2 aristas son independiente si no tienen un vértice en común, mientras que una arista relaciona 2 vértices (u, v) se dice que u y v son vértices adyacente y un bucle es una arista que relaciona con el mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden así mismo. El grado de un vértice es el número de bordes que lo conectan a un grafo.

Mientras que en un grafo existen diversas maneras de representarlo y las más destacadas por su uso son: representación grafica que consiste en un grafico en que los vértices se representan mediante puntos como grafo dirigido y grafo no dirigido. En este tipo de representación es adecuada para la interpretación y resolución de problemas en grafos pequeños o medianos. La otra representación es la relacional que consiste o se basa en la aplicación de representación en pares ordenados que compone un grafo y por ultimo tenemos la representación matricial que consiste en la matriz adyacencia y es una matriz cuadrada de n filas por n columnas, siendo n el número de vértice de un grafo.

Simplemente ciclo es un grafo que se asemeja a un polígono de n lados y consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Mientras que un camino es una sucesión de aristas de manera que, a excepción de la primera, el segundo vértice de una es el primer vértice de la siguiente.

En los tipos de grafos tenemos que los grafos planares consisten en que un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce fuera de sus extremos. Mientras que un grafo conexo de dice que un grafo G es conexo si, para cualquier par de vértices u y v en G, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repita vértices) de u a v y por ultimo un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo bipartito es un grafo G=(N, E) cuyos vértices se pueden separar en dos conjuntos disjuntos U y V. Los grafos bipartitos

...