Se nos da un DAG, necesitamos encontrar el número máximo de aristas que se pueden agregar a este DAG, después de lo cual el nuevo gráfico sigue siendo un DAG, lo que significa que el gráfico reformado debe tener la cantidad máxima de aristas, agregar incluso un solo borde creará un ciclo en el gráfico. … Continue reading «Bordes máximos que se pueden agregar a DAG para que siga siendo DAG»
Dado un grafo con n Nodes y m aristas. Encuentre el máximo número posible de Nodes que no forman parte de ningún borde (m siempre será menor o igual que un número de bordes en el gráfico completo). Ejemplos: Input: n = 3, m = 3 Output: Maximum Nodes Left Out: 0 Since it is … Continue reading «Maximice la cantidad de Nodes que no forman parte de ningún borde en un gráfico»
Dado un gráfico G , compruebe si representa una topología de bus. Una Topología de Bus es la que se muestra en la siguiente imagen: Ejemplos: Input: Output: YES Input: Output: NO Un gráfico de V vértices representa una topología de bus si cumple las siguientes dos condiciones: Cada Node, excepto los de inicio y … Continue reading «Compruebe si el gráfico dado representa una topología de bus»
Eulerian Path es un camino en el gráfico que visita cada borde exactamente una vez. El Circuito Euleriano es un Camino Euleriano que comienza y termina en el mismo vértice. Se dice que un grafo es euleriano si tiene un ciclo euleriano. Hemos discutido el circuito euleriano para un gráfico no dirigido . En esta … Continue reading «Circuito de Euler en un grafo dirigido»
Dado un grafo no dirigido y una arista, la tarea es encontrar si la arista dada es un puente en el gráfico, es decir, quitar la arista desconecta el gráfico. A continuación se muestran algunos gráficos de ejemplo con puentes resaltados en color rojo. Una solución es encontrar todos los puentes en el gráfico dado … Continue reading «Compruebe si eliminar un borde dado desconecta un gráfico»
Dado un número entero N , que representa el número de Nodes presentes en un gráfico no dirigido, con cada Node valorado de 1 a N, y una array 2D Edges[][] , que representa el par de vértices conectados por un borde, la tarea es encontrar un conjunto de como máximo N/2 Nodes tales que … Continue reading «Encuentre un conjunto de como máximo N/2 Nodes de un gráfico de modo que todos los Nodes restantes estén conectados directamente a uno de los Nodes elegidos»
Dado un grafo G , la tarea es comprobar si representa una topología en anillo. Una Topología en Anillo es la que se muestra en la siguiente imagen: Ejemplos: Input : Graph = Output : YES Input : Graph = Output : NO Un gráfico de V vértices representa una topología en anillo si cumple … Continue reading «Compruebe si el gráfico dado representa una topología en anillo»
Algoritmo de Tarjan :el algoritmo de Tarjan es un algoritmo de gráfico eficiente que se utiliza para encontrar el SCC del componente fuertemente conectado en un gráfico dirigido mediante el uso de solo unrecorrido DFSen complejidad de tiempo lineal. Laboral: Realice un recorrido DFS sobre los Nodes para que los subárboles de los componentes fuertemente … Continue reading «Comparación entre el algoritmo de Tarjan y Kosaraju»
Dado un gráfico con aristas dirigidas y no dirigidas. Se da que las aristas dirigidas no forman ciclo. ¿Cómo asignar direcciones a los bordes no dirigidos para que el gráfico (con todos los bordes dirigidos) permanezca acíclico incluso después de la asignación? Por ejemplo, en el siguiente gráfico, los bordes azules no tienen direcciones. … Continue reading «Asigne direcciones a los bordes para que el gráfico dirigido permanezca acíclico»
Dado un grafo no dirigido que consta de N vértices y M aristas y una array edge [][] , en la que cada fila representa dos vértices conectados por una arista, la tarea es encontrar el grado mínimo de tres Nodes que forman un triángulo en el gráfico . Si no existe ningún triángulo en … Continue reading «Grado mínimo de tres Nodes formando un triángulo en un Gráfico dado»