1. Es la rama de las Matemáticas Discretas que estudia los conjuntos formados por los pares vértices y aristas G = (V,A)
1.1. Aristas
1.1.1. El conjunto de aristas corresponde a una regla de correspondencia (función) entre dos vértices. Una arista indica la relación existente entre dos vértices.
1.2. Vértices:
1.2.1. El conjunto de vértices es la Unidad Fundamental del grafo. Se compone de piezas indivisibles que a su vez unen a las aristas.
1.2.2. Se dice que dos vértices son adyacentes si existen una arista que los relacione directamente. De ser el caso, a los vértices se les denomina "extremos de la arista a".
1.2.3. A su vez, al número de aristas que inciden en un vértice, se le denomina Grado o valencia. Cuando un vértice es de grado 0, es un caso especial llamado Vértice aislado.
1.3. Vértices adyacentes, extremos de la arista.
2. Representación
2.1. Matriz de Incidencia
2.1.1. Una matriz binaria en la cual las columnas representan las aristas y las filas los nodos de un grafo. Por cada nodo unido por una arista, se coloca un uno (1) en el lugar correspondiente, el resto son ceros
2.2. Matriz de Adyacencia
2.2.1. Una matriz binaria en donde tanto las filas como las columnas representan los nodos de un grafo. Se coloca un uno cuando dos nodos son adyacentes y cero en otro caso.
2.3. Función de Adyacencia
2.3.1. Representación algebraica que atiende una regla de correspondencia. Devuelve los vertices adyacente sobre cada uno que se le aplica la función
2.4. Representación Gráfica
2.4.1. Representación visual y esquemática.Los nodos suelen representarse con puntos, círculos y las aristas con líneas conectando nodos. En el caso de grafos dirigidos, se hacen con flechas y la punta indica la dirección.
3. Caminos
3.1. Camino. Una sucesión donde se alternan vértices y aristas, comenzando y terminando con vértices y en el que cada arista es incidente con los dos vértices que la preceden y la siguen.
3.2. Un ciclo es un camino en el que sus extremos coinciden. El ciclo será simple si no hay, además del primero y el ´ultimo, ningún otro vétice repetido.
3.3. Se dice que un camino de un grafo o multigrafo es de Euler si pasa por todos los vértices del mismo, recorriendo cada arista del mismo exactamente una vez.
3.4. Un ciclo simple en un grafo o multigrafo G se dice que es de Hamilton, si contiene a todos los vértices de G
4. Tipos de Gráficos y Clasificación
4.1. Por el sentido de las Aristas
4.1.1. Grafos No Dirigidos. Cuando la aristas no indican una dirección hacia el vértice. Es decir los vértices extremos (v1, v2) de la arista a, no están ordenados. Siendo equivalente v1 -> v2 que v2 -> v1
4.1.2. Grafos Dirigidos. También conocidos como dígrafos. El conjunto de las aristas está formado por pares ordenados del conjunto de vértices. Esto asigna un orden en los extremos de cada arista. Dicho orden se indica en el diagrama con una flecha y llamaremos origen o inicial al primer vértice de una arista y fin o terminal al segundo. Algunos autores llaman arcos a las aristas de los dígrafos
4.1.3. Grafos Dirigidos. También conocidos como digrafos
4.2. Por la unión de sus Vértices
4.2.1. Pseudográfos. En los que existen aristas cuyos extremos coincidan, es decir, aquellos en los que existan aristas que unan vértices consigo mismos. Estos también se llaman bucles
4.2.2. Multigrafos. En los que haya pares de vértices unidos por más de una arista.
4.2.3. PseudoMultigrafo. Cuando cumple con ambas condiciones.
4.2.4. Grafo Simple. Es el que no tiene bucles ni múltiples aristas.
4.3. Otros Grafos de Interés
4.3.1. Regular. Cuando todos sus vértices tienen el mismo grado
4.3.2. Completo. Donde cada vértice es adyacente a cualquiera de sus otros vértices
4.3.3. Vacío. Grafo donde ninguno de los vértices está relacionado. No cuenta con aristas