MATEMATIQUES 1

Preguntes de teoriaQP15

A lexamen parcial P (Teoria de Grafs) i a la part optativa F1 de lexamen final (recuperacio delparcial) hi apareixera una de les preguntes seguents:

1. - Doneu la definicio de la matriu dincidencia dun graf.

- Enuncieu i demostreu el Lema de les encaixades.

2. Sigui G = (V,A) un graf i siguin u i v vertexs diferents de G. Demostreu que si G conte dosu-v camins diferents, aleshores conte un cicle.

3. - Doneu la definicio de vertex de tall.

- Enuncieu i demostreu la caracteritzacio dels vertexs de tall.

4. - Doneu la definicio daresta pont.

- Sigui G un graf connex. Demostreu que una aresta de G no es pont si i nomes si pertanya algun cicle.

5. Enuncieu els teoremes dOre i de Dirac sobre grafs hamiltonians. Per a cadascun dells, doneuun exemple que mostri que la condicio del teorema no es necessaria i un exemple que mostrique la desigualtat que apareix en la condicio del teorema no es pot millorar.

6. - Doneu la definicio de sendero i de sendero euleria.

- Demostreu que un graf connex conte un sendero euleria si i nomes si te exactament dosvertexs de grau senar.

7. Demostreu que un graf dordre n i mida m es un arbre si i nomes si es connex i m = n 1.

8. - Doneu la definicio darbre.

- Demostreu que un graf T es un arbre si i nomes si per a cada parell de vertexs u, v hiha un unic u v cam a T .

1