Grafos
Dirigido o no, ponderado o no, con bucles y múltiples aristas. Añade y quita vértices y aristas, recórrelo en anchura y profundidad, calcula caminos más cortos con Dijkstra, orden topológico, componentes y comprobación de bipartito. Debajo, la matriz y la lista de adyacencia y todas las métricas.
Métricas
- Orden (|V|)
- 6
- Tamaño (|E|)
- 7
- Densidad
- 0.467
- Dirigido
- no
- Ponderado
- sí
- Simple
- sí
- Suma de grados
- 14
- Peso total
- 35
- Conexo
- sí
- Componentes
- 1
- Ciclos
- sí
- Árbol
- no
- Bipartito
- no
- Completo
- no
- Regular
- no
Grados
Leyenda
- Normal
- Visitado
- En la frontera (cola/pila)
- Activo
- En el camino
Matriz de adyacencia
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 4 | 2 | 0 | 0 | 0 |
| B | 4 | 0 | 5 | 10 | 0 | 0 |
| C | 2 | 5 | 0 | 0 | 3 | 0 |
| D | 0 | 10 | 0 | 0 | 4 | 0 |
| E | 0 | 0 | 3 | 4 | 0 | 7 |
| F | 0 | 0 | 0 | 0 | 7 | 0 |
Lista de adyacencia
- A → B(4), C(2)
- B → A(4), C(5), D(10)
- C → A(2), B(5), E(3)
- D → B(10), E(4)
- E → C(3), D(4), F(7)
- F → E(7)
Tipos de grafo y qué se puede comprobar
Dirigido / no dirigido: una arista tiene sentido (o no) según su dirección; el grado se cuenta por entrada, salida o total.
Ponderado: cada arista lleva un peso que usan Dijkstra y el camino más corto.
Simple / pseudografo: admite bucles; se avisa cuando el grafo deja de ser simple.
Conexo, componentes: cuántos grupos hay y si todos se alcanzan. En dirigido, la conexión fuerte exige ida y vuelta.
Árbol y ciclos: un árbol es conexo y sin ciclos.
Bipartito, completo, regular: 2-coloreable, todas las parejas unidas, y todos los grados iguales.
Suma de grados = 2·|E| en un grafo no dirigido sin bucles (lema del apretón de manos).