Grafos

wow

Grafos

¡Vamos!

Grafo dirigido Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada arista se asocia de forma unidireccional a través de una flecha con otro.

Grafo no dirigido Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a un conjunto de aristas de forma no direccional. Esto significa que una arista puede indistintamente recorrerse desde cualquiera de sus puntos y en cualquier dirección.

Subgrafo Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación). El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G

Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices. Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad. Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices. Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.

Grafo bipartito 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. Alternativamente, es un grafo con un número cromático de 2. En un grafo bipartito completo, el conjunto de vértices es la unión de dos conjuntos disjuntos, W y X, de modo que cada vértice en W es adyacente a cada vértice en X pero no hay aristas dentro de W o X.

Árbol 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 cí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.

Aquí puedes incluir un dato relevante a destacar

Aquí puedes incluir un dato relevante a destacar

Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo. Grafo vacío: aquel que no tiene aristas. Grafo trivial: aquel que tiene un vértice y ninguna arista. Grafo simple: aquel que no posee bucles ni aristas paralelas. Consultar variantes en esta definición. Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Consultar variantes en esta definición. Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1). Grafo perfecto aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.