par Rodolfo Melchor Rubio Il y a 4 années
680
Plus de détails
- Si los pesos son distintos el árbol generador es único. - El que los pesos se repitan no obliga a que existan arboles generadores del mínimo coste distintos(puede ser único o puede no ser único).
- Sea G no dirigido ponderado - El algoritmo de kruskal proporciona un árbol generador de mínimo coste - Si los pesos son distintos 2 a 2 el árbol generador de mínimo coste es único.
La relación de adyacencia entre los vértices de una gráfica 𝐺 definida por las aristas en 𝐴(𝐺) es una relación simétrica y no reflexiva. La relación “estar conectado con” sobre el conjunto de vértices de una gráfica 𝐺 es una relación de equivalencia. En un árbol 𝑇 con raíz 𝑟, la relación 𝑅 definida como (𝑢, 𝑣) ∈ 𝑅 si 𝑢 ∈ 𝑟𝑇𝑣 es un orden parcial.
- Cuando una relación es al mismo tiempo reflexiva, simétrica y transitiva se dice que es una relación de equivalencia. - Cuando una relación es simultáneamente reflexiva, anti-simétrica y transitiva se le llama un orden parcial.
- Sea G= (V,E) un grafo dirigido con raíz V_0 - Sea G=(V,E) grafo subyacente de G Se verifica que: 1.- existe un camino y solo uno desde V_0 a cada uno de los demás vértices. 2. - IEI=IVI-1 3. - G es aciclico 4. – G es conexo 5. – G es árbol
Sea G un grafo dirigido G =(V,E) Se dice que G es unn arbol con raiz V_0 si es un grafo aciclico tal que todos los vertices a excepción de V_0tienen grado de tiene uno y V_0 grado de entrada ceroentrada
Una gráfica 𝐺 es conexa si y sólo si para cualquier par de vértices 𝑢, 𝑣 ∈ 𝑉(𝐺) existe una 𝑢𝑣-trayectoria en 𝐺.
Un camino cerrado 𝑊 en el que todos los vértices son diferentes excepto el vértice inicial se llama un ciclo.
Un camino 𝑊 que no repite vértices se llama trayectoria (camino elemental).
Un camino 𝑊 que no repite aristas se denomina paseo (camino sencillo).
Cadena: toda sucesion finita alterna de vertices y aristas( resp. Arcos). Cadena cerrada: a toda cadena en la que los vertices inicial y final coinciden. Camino: a toda cadena en la que no se repiten ni vertices, ni aristas(resp. Arcos). Ciclo: cadena en la que no se repite ninguna arista (resp. Arcos)., ni vertice a escepcion del inicial y el final. Longitud de la cadena: Numero de aristas (resp. Arcos) que la conforman. Longitud de la cadena, Longitud de la cadena, Longitud del camino y Longitud del ciclo: son los espacios (uecos) entre los vertices como lo explican en el siguiente video:
Sea 𝐺 una gráfica y sean 𝑢, 𝑣 ∈ 𝑉(𝐺), entonces existe un 𝑢𝑣-camino en 𝐺 si y sólo si existe una 𝑢𝑣-trayectoria en 𝐺.
Esta clasificación es denominada como grafos etiquetados o grafos dirigidos con pesos. Este tipo de grafos concentran aristas que pueden poseer información adicional donde podemos reflejar nombres, costos, valores u otros datos. Estos grafos también son denominados como redes de actividad y el número asociado al arco, se le denomina factor de peso. Este grafo es el que más comúnmente utilizamos para representar situaciones de la vida real.
Los grafos no dirigidos son aquellos que constan un conjunto de vértices que están conectados a un conjunto de aristas de forma no direccional. Esto significa que una arista puede indistintamente recorrerse desde cualquiera de sus puntos y en cualquier dirección.
Un grafo dirigido conocido también como dígrafo consta de un conjunto de vértices y aristas donde cada arista se asocia de forma unidireccional a través de una flecha con otro. Las aristas dependiendo de su salida o ingreso reciben la calificación de entrante o saliente, la condición común, es que siempre tienen un destino hacia un nodo.
