Cyklomatické číslo (graf)
Minimální kostra grafu a šedé hrany jsou tětivy.
Cyklomatické číslo grafu je minimální počet hran takový, že po jejich odstranění nebude v grafu žádný cyklus. Cyklomatické číslo C(G) značí počet nezávislých kružnic v grafu. Pokud C(G) = 0, tak graf neobsahuje kružnice. Obecně pro každý graf existuje cyklomatické číslo, pro které platí: C(G) = E – N + P
Cyklomatické číslo je také rovno počtu tětiv. Tětivy jsou ty hrany, které zbudou potom, co se odebere minimální kostra grafu.
Média použitá na této stránce
Minimum spanning tree.svg
Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices.
Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices.