Category: Grafos

A continuación tenéis una práctica donde explico paso por paso como se obtiene warshall: Practica

A continuación explico cómo funciona el algoritmo de enumeración de grafos. Seleccionamos un vértice cuyo grado de entrada sea igual a cero, en este caso el vértice A.

PERT (Project Evaluation Research Task), Evaluación de Proyectos de Trabajo de Investigación, es una tabla que muestra una lista de actividades de un proyecto, para cada actividad existe un tiempo en días, necesario y otras actividades que deben completarse antes de poder iniciarse (prerrequisitos), a partir de las tablas representaremos los grafos ponderados. Actividad a1…

Un grafo simple G = (V,A) diremos que es un grafo ponderado si cada arista/arco tiene un peso (puede ser negativo) denotado por wij. Cada arco o arista tiene un peso, por ejemplo en el grafo dirigido Wbd = 21. Grafo A / Grafo B

Un camino Hamiltoniano en un grafo G es un camino que atraviesa cada vértice del grafo exactamente una vez. Un ciclo Hamiltoniano en un grafo G es un ciclo que atraviesa cada vértice del grafo exactamente una vez. Un grafo Hamiltoniano es aquiel grafo G que contiene un ciclo Hamiltoniano.

El algoritmo de fleury encuentra un tour o camino euleriano en un grafo no dirigido, sabiendo si existen por el siguiente teorema: Teorema 1 Sea G un grafo no dirigido y conexo – G es euleriano si y sólo si no tiene vértices de grado impar. – G contiene un camino euleriano si y sólo…

Un Tour de G: una cadena cerrada que atraviesa cada arista de G al menos una vez. Un Tour euleriano de G: una cadena cerrada que atraviesa cada arista exactamente una vez. Un Grafo euleriano es aquel en el que podemos encontrar un tour euleriano. Un Camino euleriano es una cadena o cadena simple que…

La matriz de accesibilidad representa los vértices que alcanza cada vértice, hablamos de una matriz cuadrada definida por (Rij): 1 si Vi alcanza a Vj 0 en otro caso La matriz de acceso representa los vértices que son alcanzables por otros vértices, hablamos también de una matriz cuadrada, cuyos elementos pueden ser (Qij): 1 si…

Sea G = (V,A) un grafo con n vértices y m aristas, llamamos matriz de incidencia a la matriz de orden n x m, rellenaremos la matriz con los siguientes datos: Cada columna corresponderá a una arista y cada fila a un vértice. GRAFOS NO DIRIGIDOS 0 si Vi no es incidente con la Aj…

La matriz de adyacencia de un grafo X y el número de sus vértices Y, al margen de que sea dirigido o no, será una matriz de YxY. en el caso de que tengamos un grafo con los vertices {A,B,C,D}, dibujaremos una tabla de 4×4 opcionalmente podemos señalizar las columnas y las filas con el…