Conceptes bàsics |
Conceptes bàsics: tipus de grafs (grafs simples, digrafs, multigrafs, hipergrafs), isomorfismes, subgrafs, seqüències gràfiques i teorema de Havel-Hakimi.
Alguns invariants en grafs simples (nombre de dominació, diferencial d'un grafl, nombre d'independència, nombre de cobriment de vèrtexs, 2-packing, etc) |
Operacions amb grafs |
Operacions amb grafs: Unió, suma, producte cartesià, producte corona, producte fort, producte lexicogràfic, graf línia, grafs Sierpinski generalitzats. |
Recorreguts, connectivitat i distància |
Recorreguts, connectivitat i algorismes d'exploració de grafs, grafs eulerians, grafs hamiltonians, distància i algorismes relacionats, problema de la dimensió mètrica i les seves variants, arbres (caracterització, propietats, exploració d'arbres binaris, arbre generador) |
Emparellament, planaritat i coloració |
Emparellament i aparellament perfecte, grafs planars i teorema de Kuratowski, coloració de grafs i polinomi cromàtic |