Grafo

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)[1]​ es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.[3]​ Típicamente, un grafo se representa gráficamente como un conjunto de puntos unidos por líneas (aristas o arcos).Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.Por lo general, un grafo se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes.La palabra «grafo» (en inglés, graph) fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 debido a una relación directa entre las matemáticas y la estructura química (lo que él llamó una imagen químico-gráfica).es igual al número de arcos que lo tienen como extremo.Dos o más aristas son paralelas si relacionan el mismo par de vértices.Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos.Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no.La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada.Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple.Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).En un grafo no dirigido, un par desordenado de vértices {x, y} se llama conectado si un camino lleva de x a y.En caso contrario, el par desordenado se denomina desconectado.En un grafo dirigido, un par ordenado de vértices (x, y) se llama fuertemente conectado si un camino dirigido lleva de x a y.En caso contrario, el par ordenado se denomina débilmente conectado si un camino no dirigido va de x a y después de reemplazar todas sus aristas dirigidas por aristas no dirigidas.En caso contrario, el par ordenado se denomina desconectado.En caso contrario, se denomina grafo débilmente conectado si cada par ordenado de vértices del grafo está débilmente conectado.Un grafo conectado por vértices k a menudo se llama simplemente grafo conectado por k. Un grafo bipartito es un grafo simple en el que el conjunto de vértices puede ser particionado en dos conjuntos, W y X, de modo que no hay dos vértices en W que compartan una arista común y no hay dos vértices en X que compartan una arista común.Un grafo plano es un grafo cuyos vértices y aristas se pueden dibujar en un plano de forma que ninguna de las aristas se cruce con otra.Un grafo de ciclo o grafo circular de orden n ≥ 3 es un grafo en el que los vértices se pueden enumerar en un orden v1, v2, ... , vn tal que las aristas son las {vi, vi+1} donde i = 1, 2, ... , n - 1, más la arista {vn, v1}.Un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente una trayectoria, o equivalentemente un conectado no dirigido acíclico.Un bosque es un grafo no dirigido en el que dos vértices cualesquiera están conectados por a lo sumo un camino, o equivalentemente un grafo acíclico no dirigido, o equivalentemente una unión disjunta de árboles.