Grafs
  • P: Que es un graf acíclic? Borja Soriano Maiques
    • R: Un graf sense cicles
  • P: Que es el grau d'un graf? Vicent Castell Puertas
    • R: El maxim grau dels seu vèrtex
  • P: Que representa el grau d'entrada i eixida d'un vertex d'un graf? Carlos Izquierdo Torres
    • R: El grau d'entrada és el nombre d'arestes que incideixen en un vertex i el grau d'eixida és el nombre d'arestes que emergeixen d'un vertex.
  • P: Explica les formes bàsiques en les que es pot recorrer un graf. Iván Cardona Maroto
    • R: Es pot recorrer mitjançant un recorregut en profunditat (DFS) i en amplitud (BFS).
  • Que son les components connexes en un graf no dirigit? Javier Muñoz Alcázar
    • R:
  • P: Explica quan és millor usar una representació per a grafs amb llistes o matrius d’adjacència?: Manel Lurbe
    • R:Per a representar un graf tenim dues formes: Amb llistes d’adjacència si el graf és molt dispers, és a dir, si hi ha molts més vertexs que arestes; o amb matrius d’adjacència si el graf es molt dens, és a dir que el nombre de vertex al quadrat és molt próxim al nombre de arestes, quasi complet. Depenent de les operacions més freqüents que realitzem sobre el graf podrem escollir entre una representació o un altra. Per exemple si volem saber si una aresta pertany a un graf amb llistes el cost seria lineal, recorregüent tota la llista de arestes, en canvi amb matrius seria constant.
  • P: Si no hi ha una aresta entre dos vèrtexs, podem assumir que és ? R: equivalent Miguel Tortosa Calabuig
  • P: Perquè no és possible l'ordre topològic en grafs cíclics? Izan Catalán Gallach
    • R.Perque en l'ordre topològic si existeix un camí de U a V, U sempre apareixerà primer que V, per tant si estem en un graf cíclic aquest ordre no seria possible perque tornaríem amb una aresta cap a arrere i recorreríem U i V altra vegada.
  • P:Quines son les ventajes i inconvenients d'utilitzar Llistes Enllaçades per a la implementació d'un graf? Manuel José Martínez Baños
    • R: Els avantatjes o inconvenients venen determinat amb la forma del graf. Si un graf te una cuantitat de aristes molt mes alta a la cantidad de vertex el cost de vore si un node a esta conectat a un nobe b , es linean . En canvi si ha molt de vertexs y poques arestes es una estructura ideal.
  • P: Quina diferencia hi ha en un recorregut per amplària i un recorregut per profunditat? Carles Sastre Pérez
    • R: Que en el cas del recorregut per profunditat explorem les arestes de G de manera que primer es visiten els vèrtexs adjacents als visitats més recentment, mentre que en un recorregut per amplària s'explora les arestes de G de manera que primer es visiten els vèrtexs més propers a v.
  • P: Un arbre de cobriment mínim sempre té una única solució? Christian Millán Isasi
    • R: No, perque es pot donar el cas en que els costs de les arestes siga el mateix, aleshores haurien més d'un arbre de cobriment mínim.
  • P: Quina es la forma mes eficient de inserir els elements d'un vector en un Heap ? Pablo Jimenez izquierdo
    • R:Mitjançant el metode arreglarMonticulo
  • P: Què és un ordre topològic? Sergio Bru Vidigal
    • R: és una ordenació dels vèrtexs de manera que si (o, v) € A, llavors o apareix abans que v.(La solució no és única.)
  • P: Cual es la idea fundamental del algoritmo de Kruskal? Ignacio Pacelli
    • R: Busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo.
  • P:** Quines propietats defineixen un Heap? Pablo Domingo Redolar
    • R: Propietat estructural: un heap és un arbre binari quasi complet. Propietat d'ordre: un heap es pot ordrenar com un MinHeap (la dada del node és sempre menor o igual que la dels seus fills), o com un MaxHeap (la dada del node sempre és major o igual que la dels seus fills).
  • P. Com podem saber si un vertex és assolible des de un altre? Pau Montoro González
    • R. Comprovant si trobem un cami que uneix els dos.
  • P: Quin pasos s'ha de seguir per a eliminar un element d'un monticle binari? Ivan Marsal Mascarell
    • R: - Pas 1: el mínim està en el node arrel. La dada del node arrel se substitueix llavors per l'últim element del Heap
    • - Pas 2: la nova arrel s'enfonsa a través dels seus fills fins a no violar la propietat d'ordre.
  • P: Què es un graf no dirigit? José Espasa Saval
    • R: És un parell G = (V, A) on V és un conjunt finit de vértexs y A ⊆ {{u, v} | u, v ∈ V ∧ v 6= u} és un conjunt de "parells no ordenats" de vértexs.
  • P: Quines són els components fortament connexes en un graf dirigit? Roser Fuster Bertomeu
    • R: // Són les classes d'equivalencia de vèrtexs segons la relació "ser mútuament assolible". Un graf dirigit és fortament connex si ∀o, v ∈ V, v és assolible des de o.
  • P: Defineix la propietat d'ordre d'un minHeap i d'un maxHeap? Héctor Izquierdo Ros
    • R: minHeap ->Array[pare(i)] <= Array[i], 2 <=i<=n.
    • maxHeap -> Array[pare(i)] >= Array[i], 2<=i<=n
    • on i es l'element i-ésim del array i n es el número del elements del array.
  • P: Qué es un cicle? Álvaro Salvador González
    • R: És un camí simple que comença i acaba al mateix vèrtex.
  • P:Què es un arbre de recobriment (mínim)? Eric Ferrando
    • R:Partint d'un graf connex no dirigit, l'arbre de recobriment mínim es aquell que obtenim reduint el nombre arestes per a mantindre la connexió dels vèrtex, però escollint les arestes de pes mínim.
  • P- Que fa el metode Heapify (arreglar monticulo) estudiat a clase? Julian Piqueras Gozalbes
    • R- Aquest metode restableix la propietat d'ordre a partir d'un Arbre Binari Quasi-Complet per a obtenir un Monticle Binari.
  • P:Cual es la diferencia entre un grafo etiquetado y un grafo no etiquetado? Cuando un grafo es ponderado? Rafa Castelló Giner
    • R:En los grados etiquetados las aristas llevan asociado un (dato) etiqueta y en los no etiquetados no llevan ninguna etiqueta. Un grafo será onderado si su etiqueta es un valor numérico.
  • P: Que es un grafo fuertemente conexo? Cadar, Nicolae Andrei
    • R: Un grafo es fuertemente conexo cuando dado cualquier vertice o, v pertenece a V, v es accesible desde o.
  • P:Quin és el cas favorable a l'inserir un element en un minHeap? Alexis Gil Calatayud
    • R:Quan sols haja de fer una comprovació, és a dir, quan l'element a inserir és major que el seu pare.
  • P- Qué vol dir que un vèrtex és assolible des d'un altre vèrtex? Sergio Rubio Salvador
    • R- Direm que un vèrtex es assolibre desde altre vèrtex cuan existeix un camí des de un a l'altre.
  • P:Quina es la forma mes eficient d'inserir elements d'un vector en un Heap? Sergio Añón
    • R: mitjançant el metode arreglarMonticulo
  • P- Què és un graf? Daniel Stanislowsky López
    • R- Una ferramenta matemàtica per a modelar relacions binàries entre elements d'un conjunt.
  • P: Podem considerar un graf d'ordre topològic si un dels seus nodes està aillat? Francesc Fernandez Costa
    • R: Sí, ja que no infringeix la norma de que una volta ordenats els vèrtex en línia no hi ha cap aresta que torne cap enrere.
  • P- Cuando un vertice u, es adyacente a un vertice v? Alejandro Andion Pereira
    • R-Cuando existe una arista que los conecta
  • P- El recorregut en amplada d'un graf és únic? Vicent Ahuir Esteve
    • R- No és únic, ja que l'ordre en que visitem els adjacents d'un mateix vertex modificarà el recorregut en amplada.
  • P- En Kruskal quina aresta hem de triar en cada nivell de l'arbre de decisions? Fernando Alcina Sanchis
    • R - Hem de triar l´aresta de menor pes i que no cree cicle.
  • P- En un minHeap on podrem trobar el màxim? # Carlos Herrero Barberá
    • R- El màxim estarà en una de les fulles, per tant el podrem trobar entre [(elArray.length/2) + 1 , elArray.length]
  • P- Al algorisme de Kruskal, com seleccionem eficientment l'aresta de menys pes en cada iteració ? Imanol Carbonell
    • R- Hem de mantindre les arestes en una cua de prioritat ( per exemple, un minheap ) organitzades segons el seu pes.
  • P- Quina ventaja presenta a nivell d'implementació el recorregut en profunditat d'un graf? Sergio Turo Roldán
    • R- Aquesta estratègia admet una implementació simple de forma recursiva, utilitzant globalment un comptador i un vector de naturals per a marcar els vèrtexs ja visitats i emmagatzemar l'ordre de recorregut.
  • P- Quantes formes fonamentals existeixen de representar un graf? Juan Jordá Pérez
    • R- Llistes de adjacència si el graf es molt dispers o matriu de adjacències si el graf és molt dens.
  • P: Com s'elimina correctament el mínim d'un minHeap (arrel)?Pau Sastre Pons
    • R: Canviem l'arrel per lúltime element del Heap (talla) i reduïm la talla. Després hem d'enfonsar el nou element que hi ha a l'arrel, ja que no complirà les propietats d'un minHeap. A l'enfonsar anem comparant entre els fills, va intercanviant-se pel fill més menut fins que complix l'ordre.
  • P: Com se inserix un nou element en el Monticle Binari? Quin cost te? Francesc Sanchez Guinart
    • R: Per a inserir un nou element al monticle binari se recorre el vector i se inserix en la primera posicio disponible (elArray[talla +1 ]) despres se va comparant en els seus anteriors per a que "reflote" fins que no viole el orden. El cost de inserir es O(log2N) per al pitjor cas, per al millor cas sols es necesita una unica comparació.
  • P: Quin és el resultat de l'algoritme de Kruskal? Joan Moltó Balaguer
    • R: Un arbre lliure (no arrelat) format pels mateixos vèrtexs amb el mínim nombre d'arestes la suma de les quals la mínima posible.
  • P: Quina peculiaritat té el heap a l'hora de desplaçar-se per ell? Carlos Martínez Leante
    • R: Els nodes s'emmagatzemen en un array segons el seu recorregut per nivells (deixant la posició 0 de l'array buida per a que siga més fàcil calcular les posicions) donat un node pare N[i], el seu fill esquerre es trobarà en la posició N[2*i] i el fill dret es trobarà en la posició N[2*i+1].
  • P: Podem afirmar que la propietat estructural d'un heap es que es un arbre binari complet? Javier Cholbi Pascual
    • R:No, ja que es un arbre binari quasi-complet.
  • P: En el tema de grafs, que aconseguim amb el algorisme de Dijkstra? Rubén Vivas Alegre
    • R: Aconseguim processar els vèrtexs i arestes una sola vegada.
  • P: En que es basa el metode Heapify? I quin es el seu cost? Juan Ignacio Soler Suarez
    • R: Es basa a enfonsar els nodes en ordre invers al recorregut per nivells. El cost de arreglar un monticle es O(n)
  • P: Quina és la diferéncia entre un camí i un camí simple? Guillermo Olmeda Zurriaga
    • R: Un camí simple, és un camí en el qual tots el seus vèrtexs són diferents(exceptuant primer i últim).
  • P: Donat un exemple de graf obtingut per la sortida estàndard, com podem saber si és dirigit o no? Héctor LLoria Jaén
    • R: Hem de fixar-nos en les relacions entre vèrtexs (arestes), si apareixen els mateixos però al revés és no dirigit (en ambdós sentits); en cas que apareguin una vegada, és dirgit (en un sentit)
  • P: Quin algorisme utilitzem per calcular el camí de menys pes en el cas d'un graf acíclic? I en un graf amb cicles i pesos positius? Borja García Alonso
    • R: En el primer cas utilitzarem tècniques de programació dinàmiques. En el segon utilitzarem l'algorisme de Dijkstra.
  • P : ¿Quina és la mitjana de comparacions per a dur a terme una inserció? Juan José Pastor Lozano
    • R: 2.6 comparacions
  • P : Quan un graf es pot considerar com a dens? I com a dispers? Jorge López Ribes
    • R : Dens ( |A| ≈ |V|2) Dispers ( |A| «< |V|2)
  • P: ¿En un Heap, segons la seua estructura, ens pot assegurar sempre un cost quadràtic en el pitjor cas? Daniel Aibar Gimenez
    • R : No es correcte, ja que si impliquen l’exploració d’una branca sencera, segons la seua estructura en el pitjor cas ens pot assegurar un cost logarítmic, es mes, en qualsevol altra situació podria ser qualsevol cost.
  • P: Quin es el cost temporal d'ordenar un graf en ordre topològic? Ferran Mora Espí
    • R: O(|V| + |A|). (El cost del DFS).
  • P: Es la seqüència {16,14,10,8,7,9,3,2,9} un maxHeap? Javier Ruiz Vila
    • R: No, L'ultima fulla hauria de ser menor que el seu pare (el 7)
  • P: Quin es l'objectiu principal de l'algoritme de Dijkstra? Saúl Cerdá Peris
    • R: Obtindre a partir d'un graf i un vertex seleccionat com a origen, el cami minim entre el vertex seleccionat com a origen i qualsevol altre.
  • P: Quin és el cost del algorisme d'ordenació HeapSort? Jose Garabal Esteban
    • R: El cost es O(N ∗ log2N)
  • P: Que es un Subgraf? I un subgraf induït? Jordi Almendros Granero
    • R: Un subgraf és un graf que esta format part o la totalitat de l'estructura d'un graf major. Un subgraf induït és un subgraf que especifica els nodes que es queden eliminant els restants junt amb totes les seues relacions.
  • P:Quines son les propietats d'un heap? Artur Monter Anduix
    • R:Estructural: es un arbre binari quasi-complet D'ordre : en un minHeap, la dada d'un node és sempre menor o igual que el dels seus fills, mentre que en un maxHeap és sempre major o igual
  • P: Que és la intersecció de dos grafs? Javier Chorro Bisquert
    • R: És un altre graf amb només aquelles arestes i vértex que estan en tots dos grafs.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License