Algoritmica grafurilor (Radu-Dragos Popescu)

Cursuri

Descriere

• 2 ore de curs / saptamana.
• 2 ore de seminar / saptamana.
• 1 ora de laborator / saptamana.

Structura:

1. Matrici asociate unui graf.
2. Parcurgeri pe un graf.
3. Matricea drumurilor intr-un graf. Algoritmul Roy-Warshall.
4. Abori de pondere minima. Algoritmul lui Prim, algoritmul lui Kruskal.
5. Distante si drumuri minime in grafuri. Algoritmul Roy-Floyd, algoritmul Dantzig, algoritmul Dijkstra.
6. Cicluri euleriene. Algoritmul Fleury.
7. Cicluri hamiltoniene optime. Algoritmul lui Christofides.
8. Cuplaje. Problema repartitiei optime. Algoritmul Kuhn-Munkres.
9. Fluxuri in retele. Algoritmul Ford-Fulkerson. Teorema lui Menger.

2, http://cheapmedsonline.co.uk/ cialis price,

Notare

Bibliografie

• Dragos-Radu Popescu - "Combinatorica si algoritmica grafurilor" - Biblioteca Societatii de Stiinte Matematica, 2007

Subiecte date la examen

Din urmatoarele subiecte alege doua. Al treilea subiect este o problema

1. MULTISETUL GRADELOR UNUI GRAF SIMPLU. (*******)

          Definitii. Notatii. 
          Teorema  HAVEL – HAKIMI.

2. GRAFURI BIPARTITE. (*******)

            Definitie. 
            Teorema  lui  KONIG. 

3. GRAFURI PLANARE. (*******)

             Definitii. Notatii. 
             Teorema  poliedrala  a  lui  EULER. 
              

4. ARBORI PARTIALI ECONOMICI si AI DISTANTELOR.

               Definitii.Notatii.Scop. 
               Algoritmii  lui  PRIM  si  DIJKSTRA 

5. ARBORI PARTIALI ECONOMICI.

                Definitii. Notatii. Scop. 
                Algoritmii  PRIM , KRUSKAL si  BORUVKA. 

6. CUPLAJE . (*******)

                Definitii. Notatii. Scop.
                Diferenta simetrica a doua cuplaje. 
                Teorema lui BERGE.

7. CUPLAJE in GRAFURI BIPARTITE.

                 Definitii. Notatii. Elemente pregatitoare.
                 Teorema  lui  HALL. Aplicatii.

8. CUPLAJE PERFECTE in GRAFURI BIPARTITE.

               Definitii. Notatii. Scop.
               Elemente pregatitoare. 
               Algoritmul  UNGAR. 

9. CUPLAJE DE PONDERE MAXIMA in GRAFURI BIPARTITE.

               Definitii. Notatii. Scop. 
               Elemente pregatitoare.
               Algoritmul  KUHN – MUNKRES. 

10. LINII HAMILTONIENE. (*******)

              Coditii  suficiente  de  hamiltoneitate.
              Teorema  lui  Dirac. 

11. LINII HAMILTONIENE.

              Algoritmul  lui  Cristofides  pentru  determinarea  unui  lant  hamiltonian
              de  pondere  minima.

12. RETELE DE TRANSPORT.

               Definitii. Notatii. Scop. 
               Elemente pregatitoare. 

Subiecte 2008:

• Subiectul I:
  • Multisetul gradelor unui graf simplu
  • Cuplaje in grafuri bipartite - Teorema lui Hall.
  • o problema cu un graf - sa arati ca e hamiltonian
• Subiectul II:
  • Proprietati ale arborilor
  • Hamiltoneitate - Teoremele lui Dirac si Ore.
  • orice graf planar cu gradele varfurilor >2 are cel putin o fata de grad <=5
• subiectele de teorie au fost date ca mai sus, insa problemele au avut variatii, dar de acelasi tip.
• Probleme pe numere:
  • nr 1.:
    1. (1p) Fie G un graf planar, G conex, a. i. gradul fiecarui varf sa nu fie 1, 2 sau 3. Sa se demonstreze ca harta asociata lui G are o fata de grad <=3.
  • nr 2:
    1. Problema alcatuita din doua subpuncte:
       • a) (0,25p) Se da un graf (desenat pe tabla) Sa se demonstreze ca G e graf hamiltonian (aici trebuie ingrosat ciclul hamiltonian gasit care demonstreaza ca G e hamiltonian)
       • b) (0,75p) Sa se demonstreze ca nu exista un ciclu hamiltonian care cuprinde simultan 4 din muchii (aici daca nu ma insel, demonstratia se facea folosit teorema lui Grinberg amintita la seminar)
• Observatii:
  • fiecare subiect de teorie are 3 puncte (restul de 3 sunt pe proiect)
  • se noteaza cu 1 punct teoremele, fara demonstratii, pentru fiecare subiect in parte.

142:

• Nr. I:
  1. Grafuri bipartite. Teorema lui Konig.
  2. Hamiltoneitate. Ore si Dirac.
• Nr. II:
  1. Grafuri planare. Teorema poliedrala a lui Euler.
  2. Cuplaje. Teoremele lui Berge si Hall.