Explorando Grafos y Árboles: Conceptos y Algoritmos Clave
Enviado por Programa Chuletas y clasificado en Matemáticas
Escrito el en español con un tamaño de 6,12 KB
Conceptos Fundamentales de Grafos
Grafo Completo (Kn)
Un grafo completo es aquel donde todos los vértices están conectados entre sí. El número de aristas en un grafo no dirigido es n*(n-1)/2, y en un grafo dirigido es n*(n-1), donde 'n' es el número de vértices.
Grafo Bipartito (Km,n)
En un grafo bipartito, los vértices se dividen en dos conjuntos disjuntos, y las aristas solo conectan vértices de conjuntos diferentes. Los vértices de un mismo conjunto no pueden ser adyacentes. El número máximo de aristas en un grafo bipartito es (n2)/4 (cuando los dos conjuntos tienen el mismo número de elementos, o lo más cercano posible).
Subgrafos
- Subgrafo Propio: Contiene un subconjunto de vértices y aristas del grafo original, verificando que