Grafs
  • Què és el grau d'entrada d'un vertex v? I el grau d'eixida? José Joaquin Rubio Iñigo
    • El grau d'entrada és el nombre d'arestes que incideixen en v.
    • El grau d'eixida és el nombre d'arestes que emergeixen de v.
  • Que es un grafo no dirigido? Víctor Costa Vidal
    • Un grafo no dirigido es aquel en el que sus aristas no están orientadas en ningún sentido.
  • Quina diferència hi ha entre un graf dirigit i un graf no dirigit? Javier Martínez Bernia
    • En un graf dirigit les arestes només tenen una direcció i en un graf no dirigit les arestes no tenen direcció (van en els dos sentits).
  • Quin es el grau de un vértex en un graf no dirigit? Jose Daniel Ferrando Ferrer
    • El grau de un vértex en un graf no dirigit es el nombre de aristes que incideixen sobre ell (o de vértex adjacents).
  • Què és un camí simple? Elena Garrigós Candela
    • Camí en el qual tots els seus vèrtexs diferents, excepte pot ser el primer i l'últim.
  • Que es un graf ponderat? Pablo Pérez Mas
    • És un graf etiquetat amb nombres reals.
  • Que es un cicle en un graf? Pablo S. Díaz Castelló
    • És un camí simple hv0, v1, … , vk i tal que v0 = vk i el camí conté almenys una aresta.
  • Que es el grau d'un graf? David García Agost
    • És la suma dels graus d'entrada i eixida
  • Defineix els mètodes per a recorrer un graf de forma sistemàtica i eficient. Albert Grau Anguera
    • Recorregut en profunditat: generalització del recorregut en preordre d’un arbre.
    • Recorregut en amplitud: generalització del recorregut en nivells d’un arbre.
  • Què és un graf complet? Arnau Ruiz Fuster
    • Un graf complet és aquell en el qual hi ha una aresta per cada parell de nodes diferents dels graf.
  • Com es la funció de recorregut en amplària d'un graf? Vicent Martinez Chulvi
    • La funció de recorregut en amplaria obté un recorregut en amplària de G cridant a la rutina BFS.
    • S’utilitza globalment un comptador "n" i un vector de naturals "visita" per a marcar els vèrtexs ja visitats "visita[v] > 0" i emmagatzemar l’ordre de recorregut.
    • BFS utilitza una cua auxiliar Q per a gestionar els vèrtexs no visitats.
  • Que es un graf? Àngel Chirlaque Zapata
    • Una ferramenta matemàtica per a modelar relacions binàries entre elements d’un conjunt.
  • Quines dues formes fonamentals hi ha de representar un graf? Jesús Yáñez Signes
    • Si el graf és molt dispers : Llistes de adjacència
    • Si el graf és molt dens: Matriu de d’Adjacències
  • Que permet un graf? Raúl Talens Ferrer
    • Permet expressar d’una forma visualment molt senzilla i efectiva les relacions que es donen entre elements de molt diversa índole.
    • Des d’un punt de vista pràctic, els grafs permeten estudiar les interrelacions entre unitats que interactuen unes amb unes altres.
  • Que es un graf etiquetat? Héctor Serrano Estellés
    • Graf etiquetat: és un graf G = (V, A) acompanyat d’una funció f : A → E, on E és un conjunt les components del qual es denominen etiquetes.
  • On podem trobar grafs en les aplicacions? Ana Maria Adam Liberos
    • Indexació de pàgines web. Cada pag es un vèrtex i els links són les arestes
    • Xarxes socials.
    • Internet
    • Testeig de models: chips, codi, autòmates, etc
  • Qué és l'ordre topològic d'un graf dirigit? Vicent Arnau
    • És una ordenació dels vèrtexs d'un graf G(V,A) de manera que si (o,v)∈A, o apareix abans que v.
  • Que es el grau d'un vèrtex? Jordi Belda Felipe
    • El grau d'un vèrtex és la suma dels graus d’entrada i eixida del vèrtex
  • Que és la longitud d’un camí en un graf? Arnau Mompo Alepuz
    • La longitud d'un camí és el nombre d’arestes que ho formen.
  • Cóm es pot representar un graf en una Matriu d'adjacència? Joan Ramón Esteve Chulià
    • Primerament, creem una matriu quadrada G:[V][V] de booleans on V és el nombre de vèrtex.
    • A continuació, posem a true G [u][v] on (u,v ) és una aresta del graf.
    • Repetim aquest pas fins a representar totes les arestes.
  • En que consisteix l'idea voraç de l'algorisma de Dijkstra? Joan Vicent Pedro Martí
    • Començant en el vèrtex origen S, construir incrementalment camins als altres vèrtexs seleccionant en cada pas un vèrtex V no seleccionat anteriorment que tinga el camí més barat fins a ell.
  • Quines dos formes fonamentals de representar un graf hi han? Quan s'ha d'emprar casacuna? Francesc Ferrer Pérez
    • La matriu d'adjacències i la llista d'adjacència. Quan el graf es molt dispers, s'utilitza la matriu d'adjacències(|A|«<|V|2); i quan el graf es molt dens(|A|≈|V|2), s'utilitza la llista d'adjacència.
  • Quins tipus de recorreguts en grafs coneguem ? Sergi Vendrell García
    • Recorregut en profunditat DFS i en amplaria BFS.
  • Quina diferència hi ha entre un graf dirigit i un no dirigit? Àngel Giner Vidal
    • Que a un graf dirigit, una aresta representa el camí d'un vertex a un altre en una direcció, en canvi, a un graf no dirigit, la mateixa aresta serveix per a represenar un camí en ambdues direccions.
  • En que consisteix un recorregut en profunditat? Jesús Peiró López
    • Es un recorregut que explora sistemàticament les arestes del graf de manera que primer es visiten els vèrtexs adjacents als visitats més recentment. D’aquesta forma, es va aprofundint en el graf.
  • En l'algorisme de Kruskal, com seleccionem eficientment l’aresta de menor pes en cada iteració? Álvaro Salvador González
    • Mantenint les arestes en una cua de prioritat organitzades segons el seu pes.
  • Què és un bucle a un graf? Maria Ribes de la Concepción
    • Un bucle és un cicle de longitud 1.
  • Què és el grau d'eixida d'un vértex? Javier Contrí González
    • El grau d'eixida d'un vértex és el nombre d'arestes que emergeixen d'ell.
  • L'orde topològic és possible en els grafs cíclics o acíclics? Laura Medina Chaveli
    • En els acíclics, ja que no és possible l’ordenació topològica quan existeixen cicles.
  • Que és un arbre de recobriment d’un graf no dirigit G = (V, A)? Vicente Gavilá Buigues
    • És un arbre lliure T = (V', A') tal que V' = V i A' ⊆ A i |A| = |V| - 1.
  • Com funciona l'algorisme de Kruskal? Guillermo Montilla Tomás
    • Busca un subconjunt d'arestes que, formant un arbre, inclouen tots els vèrtexs i on el valor total de les arestes de l'arbre és el mínim. Si el graf no és conex, llavors es busca un bosc expandit mínim (un arbre expandit mínim per a cada component conexa).
  • Què es una matriu d'adjacència? Joaquim Brines i Garcia
    • La matriu d'adjacència és aquella matriu on les files i columnes representen cada vèrtex del graf. Si hi ha relació es coloca un 1 representant aquesta, sino un 0.
  • En l'algoristme de Kruskal com verifiquem eficientment la condició de “no crear cicle”? Genis Martinez Sanchis
    • Mantenint una col·lecció de subconjunts disjunts amb els vèrtexs de cada arbre del bosc: Una aresta (o, v) no crearà cicle si o i v estan en diferents subconjunts.
  • Què és el grau d'entrada d'un vértex v? Víctor Cardona Lorenzo
    • El grau d'entrada d'un vértex és el nombre d'arestes que incideixen en v.
  • ¿Que es un grafo? Miguel Ángel Mateo Casali
    • Un grafo es una representación gráfica de entidades representadas como vértices, y sus relaciones representados mediante aristas.
  • Es por utilitzar l'algoritme de Dijkstra a un graf on hi han arestes amb pes negatiu? Juan Carlos Criado Beltrán
    • No, ja que l'algoritme requereix pesos positius en totes les aristes del graf.
  • Que aplicació té l'estratègia de recorregut en amplària d'un graf? Stella Esparza Torregrosa
    • El recorregut en amplària permet l'exploració parcial d'un graf de grandària elevada i també trobar el camí més curt entre dos nodes.
  • Que és un graf acíclic? Iris López Martínez
    • És un graf que no conté cicles.
  • Un graf no dirigit te ordre topologic? Antonio Vte. Molines Martin
  • No, ja que per a tindre ordre topologic ha de poderse colocar de forma que totes les arestes avancen, si no es dirigit la mateixa aresta va cap avant i cap arrere*
  • En un graf, que es un vèrtex assolible des d'un altre vèrtex u? Antonio Manuel Sirvent Juan
  • És qualsevol vèrtex v per al qual existeix un camí de u a v.
  • Que són les components fortament connexes d'un graf? Cristian Medina Azorín
  • Es tracten de les classes d’equivalència de vèrtexs segons la relació “ser mútuament assolible”.
  • Que són les components connexes en un grad no dirigit? Tomás Ruiz Martín
  • Són les classes d'equivalència de vèrtexs segons la relació "ser assolible"
  • ** Que es un graf dirigit? Y qué és el grau d'entrada i el grau d'eixida d'un graf? Jean Fernandes.
  • Els camins entre nodes son unidireccionals. El grau és el nombre de camins que tenen com a fi u origé un node.
  • Quina informació podem obtindre de la llista d'adjacència d'un vèrtex v a l'hora de representar un graf? Miguel Alejandro Muñoz Gil
  • La llista d'adjacència representa les arestes que tenen com a origen el vèrtex v en forma de llista, d'on podem extraure tant el pes com el destí d'aquestes arestes. La qual cosa ens permet obtindre els vèrtex adjacènts a v (destins de les arestes)
  • Quin tipus de recorregut hem de fer per tots els nodes del graf per tal de poder calcular si segueix un ordre topològic? Marc Gavilán Gil
    • Hem de fer un recorregut en profunditat(DFS) i representar els nodes en l'ordre invers en que hem fet el recorregut.
  • Quina es la definició de camí? María Alabau Bosque
    • És una seqüència (v0, v1,…,vk) de vèrtex de G = (V , A) tal que v0 = o, vk = v, (vi, vi+1) ∈ A, 0 ≤ i < k
  • Quina es la idea voraç de l'algorisme de Kruskal? Aitana Villaplana
    • Construir incrementalment un bosc (de recobriment), seleccionant en cada pas una aresta (o, v) ∈ A tal que:
      • No es creu cap cicle.
      • Produïsca el menor increment de pes possible.
  • Quin és el cost aproximat de l'algorisme de Dijkstra amb llistes d'adjacència? Miguel García Bohigues
    • Fem X operacions d'extracció sobre un vector amb cost O(|V|) cadascuna
    • Des de cada vèrtex s'examina una unica aresta cada volta. Sabem que hi ha Y arestes i el cost de cada iteració es O(1). Així donç el cost de recorrer le llistes d'adjacència és O(|A|)
    • Per tant, el cost total de l'algorisme es O(|V|^2 + |A|)
  • Que dos estructures de dades permeteixen representar l'informació d'un graf en l'ordinador? Joan Cervera Buigues
    • Matriu d'adjacències
    • Llistes d'adjacències.
  • Què va donar orige a la teoria de grafs? Jaume Murgui Gómez
    • La resolució del problema dels ponts de Königsberg per part de Leonhard Euler
  • Quan es dona que l’algorisme de cerca primer en amplària des d'un node, proporciona els costos d'aquest a tots els altres vèrtexs? Pilar Piqueres Matoses
    • Quan tots els arcs tenen el mateix pes i aquest és positiu.
  • Que és l'ordre topològic d'un graf? Sergio López Coll
    • Es la capacitat de representar un graf acíclic d'una forma linial, sense cicles ni arestes que senyalen un vertex situat darrere.
  • Com funciona l’estratègia de recorregut en profunditat DFS? Mireia Vico Burruezo
    • Donat un graf G = (V, A) i un vèrtex v ∈ V, explora sistemàticament les arestes de G de manera que primer es visiten els vèrtexs adjacents als visitats més recentment. D’aquesta forma, es va aprofundint en el graf; és a dir, allunyant-se progressivament de v

Qué es un cicle? i un bucle? Robert Muradyan
*Un cicle es un camí simple amb un determinat nombre de vertexs (k) on el primer vertéx (v0) es igual al últim (vk) i conté almenys una aresta.
*Un bucle es un tipus de cicle amb longitud 1.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License