La palabra grafo proviene del griego graphein, que quiere decir escribir o grabar. Se conoce como grafos a aquellas estructuras compuestas por aristas o arcos y los vértices o nodos, los cuales unen los vértices uno a los otros.
Los grafos están compuestos por aristas, que son las líneas con las cuales se unen los vértices; por vértices, que son los elementos de conformar un grafo; y por el camino, que es la serie de vértices que están interconectados por aristas.
En el área de la lingüística, un grafo llega a ser un objeto unitario y abstracto que enmarca las grafías que conforman una determinada letra. Como tal el término procede del griego y quiere decir dibujo o imagen.
Tipos de grafos
Grafo dirigido
Se refiere a los grafos que presenta sus grafos orientados por flechas.
Grafo no dirigido
Dícese del tipo de grafo que no tienen flecha, o sea no están orientados.
Multigrafo
Refiere al tipo de grafo que puede aceptar entre sus dos vértices a más de una arista, las cuales se nombran como lazos o aristas múltiples. De estos tipos de grafos se destacan los grafos simples, los cuales se les suele llamar como grafo general.
Grafo bipartido
Se refiere al tipo de grafo que con sus vértices se pueden crear dos conjuntos disjuntos, donde no habrá adyacencias entre los vértices que conforman el mismo conjunto.
Grafo simple
Es el tipo de grafo que solo puede aceptar entre sus dos vértices una sola arista, la cual llegará a unir estos dos vértices. Se forma por un conjunto V de puntos que se le conoce como nodos o vértices.
Grafo orientado
También se le conoce como digrafo o grafo dirigido. Se trata de los grafos a los cuales se adiciona una orientación a las aristas, la cual se suele distinguir con el uso de una flecha.
Grafo nulo
Son aquellos grafos que no tienen conectados sus vértices, o sea, sus vértices están aislados.
Pseudografo
Tipo de grafo que suele contener algún tipo de lazo.
Grafo isomorfos
Se forman cuando en dos grafos hay una correspondencia biunívoca en sus vértices, donde dos de ellos se unen por una arista en común.
Grafo regular
Se dice del grafo que tiene igual grado de valencia en todos sus vértices.
Grafo plano
Se trata de los grafos donde sus aristas y vértices pueden representarse sin interacción alguna entre ellos. Un grafo puede ser plano debido al Teorema de Kuratowski.
Grafos platónicos
Se refiere a los grafos conformados por las aristas y vértices de los cinco sólidos Platónicos o regulares, como es el octaedro, el cubo, el icosaedro, dodecaedro, etc.
Grafo etiquetado
Se refiere a los grafos donde se adiciona a las aristas un peso, el cual muchas veces es un número entero, o se suele añadir a los vértices una etiqueta.
Grafo infinito
Son aquellos compuestos por una serie de aristas y vértices de cardinal infinito.
Grafo aleatorio
Son aquellos que tienen asociadas todas sus aristas a una probabilidad.
Hipergrafo
Dícese de los grafos que sus aristas tienen como mínimo dos extremos.
Grafo completo
Conformado por un grafo simple con una sola arista en medio de dos vértices diferentes. Es el tipo de grafo que muestra dos vértices interconectados.
Grafo árbol
Se trata de un grafo conexo T carente de ciclos, lo cual tambien se le conoce como árbol libre.
Grafo conexo
Tipo de grafo que solo posee un camino simple en cualquiera de sus nodos.