Categoría: Graph

NetworkX: paquete de software de Python para el estudio de redes complejas

Posted on by Rudeus Greyrat

NetworkX es un paquete de software en lenguaje Python para la creación, manipulación y estudio de la estructura, dinámica y función de redes complejas. Se utiliza para estudiar grandes redes complejas representadas en forma de gráficos con Nodes y aristas. Usando networkx podemos cargar y almacenar redes complejas. Podemos generar muchos tipos de redes aleatorias … Continue reading «NetworkX: paquete de software de Python para el estudio de redes complejas»

Clasificación topológica

Posted on by Rudeus Greyrat

  La ordenación topológica para el gráfico acíclico dirigido (DAG) es una ordenación lineal de vértices tal que para cada arista dirigida uv, el vértice u viene antes que v en la ordenación. La clasificación topológica de un gráfico no es posible si el gráfico no es un DAG. Por ejemplo, una clasificación topológica del … Continue reading «Clasificación topológica»

Aplicaciones de la primera búsqueda en profundidad

Posted on by Rudeus Greyrat

  La búsqueda en profundidad (DFS) es un algoritmo (o técnica) para recorrer un gráfico. DFS utiliza una estructura de datos de pila para el recorrido. Un gráfico puede tener más de un recorrido DFS. Los siguientes son los problemas que usan DFS como bloque de construcción.   1) Detección de ciclo en un gráfico  … Continue reading «Aplicaciones de la primera búsqueda en profundidad»

Ruta más corta en un gráfico ponderado donde el peso de un borde es 1 o 2

Posted on by Rudeus Greyrat

Dado un gráfico dirigido donde cada borde tiene un peso de 1 o 2, encuentre el camino más corto desde un vértice de origen dado ‘s’ hasta un vértice de destino dado ‘t’. La complejidad de tiempo esperada es O(V+E).  Una solución simple es usar el algoritmo de ruta más corta de Dijkstra , podemos … Continue reading «Ruta más corta en un gráfico ponderado donde el peso de un borde es 1 o 2»

Contar el número de aristas en un gráfico no dirigido

Posted on by Rudeus Greyrat

Dada una representación de lista de adyacencia gráfica no dirigida. Escribe una función para contar el número de aristas en el gráfico no dirigido. Complejidad de tiempo esperada : O(V) Ejemplos: Input : Adjacency list representation of below graph. Output : 9 La idea se basa en Handshaking Lemma. El lema del apretón de manos … Continue reading «Contar el número de aristas en un gráfico no dirigido»

Problema de matrimonio estable

Posted on by Rudeus Greyrat

El Problema del Matrimonio Estable establece que dados N hombres y N mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto en orden de preferencia, casar a los hombres y mujeres juntos de tal manera que no haya dos personas del sexo opuesto que prefieran tener ambos. entre sí que sus … Continue reading «Problema de matrimonio estable»

Prueba de que el problema de decisión de camarilla es NP-Completo

Posted on by Rudeus Greyrat

Requisito previo: NP-Completitud Una camarilla es un subgrafo de un grafo tal que todos los vértices en este subgrafo están conectados entre sí, es decir, el subgrafo es un grafo completo. El problema de la camarilla máxima es encontrar la camarilla de tamaño máximo de un gráfico G dado, que es un gráfico completo que … Continue reading «Prueba de que el problema de decisión de camarilla es NP-Completo»

Encontrar la ruta más corta entre dos Nodes cualquiera usando el algoritmo de Floyd Warshall

Posted on by Rudeus Greyrat

Dado un gráfico y dos Nodes uyv , la tarea es imprimir el camino más corto entre uyv usando el algoritmo de Floyd Warshall . Ejemplos: Entrada: u = 1, v = 3   Salida: 1 -> 2 -> 3  Explicación:  El camino más corto de 1 a 3 es a través del vértice 2 con … Continue reading «Encontrar la ruta más corta entre dos Nodes cualquiera usando el algoritmo de Floyd Warshall»

Algoritmo de Boruvka | Codicioso Algo-9 – Part 1

Posted on by Rudeus Greyrat

Hemos discutido los siguientes temas sobre el árbol de expansión mínimo. Aplicaciones del problema del árbol de expansión mínimo Algoritmo del  árbol de expansión mínimo de Kruskal Algoritmo  del árbol de expansión mínimo de Prim En esta publicación, se analiza el algoritmo de Boruvka. Al igual que el de Prim y el de Kruskal, el … Continue reading «Algoritmo de Boruvka | Codicioso Algo-9 – Part 1»