Graphes non orientés

Définir et illustrer les notions suivantes : graphe fini (non orienté), ordre, graphe pondéré, liste d'adjacence.

Graphe fini : Ensemble fini d'arrêtes et de sommets.
Ordre: Nombre de sommets du graphe
Graphe pondéré : Graphe où chaque arête à une valeur numérique.
Liste d'adjacence : Représentation d'un graphe sous forme de liste. On liste, pour chaque sommet, ses sommets adjacents.\

Définir et illustrer mes notions suivantes : graphe simple, multigraphe, p-graphe, graphe complet, graphe bipartie/biparti complet.

Graphe simple : Un graphe est simple si une arête relie au plus 2 sommets et n'a pas de boucle sur un sommet.
Multigraphe : Contraire au graphe simple.
P-graphe : Graphe mutligraphe pour lequel il y a au plus p arêtes entre 2 sommets.
Graphe complet : Si chaque sommet du graphe est relié directement à tous les autres sommets.
Graphe biparti : Si ses sommets peuvents être divisé en 2 ensembles X et Y, pour que chaque sommet de X soit lié à au moins un sommet de Y et vice versa.
Graphe biparti complet : Graphe biparti où chaque sommet de X est relié à tous les sommets de Y et vice versa.

Définir et illustrer les notions suivantes : graphe connexe, non connexe, pont, graphe partiel, sous-graphe, clique.

Graphe connexe : possible d'atteindre n'importe quel sommet depuis un sommet de départ en suivant les arêtes.
Grpahe non connexe : se décompose en plusieurs composants connexes.
Pont : Est une arête si quand elle est supprimée, ça augment le nombre de composantes connexes.
Graphe partiel : Graphe où on a enlevé des arêtes.
Sous-graphe : Grpahe où on a enlevé un ou plusieurs sommets (et ses arêtes associées).
Clique : sous-graphe complet d'un graphe.

Définir et illustrer les notions suivantes : dégré d'un sommets, degré d'un graphe nnon orienté, graphe k-régulier.

Degré d’un sommet : nombre d’arêtes associées à ce sommet et noté d(v).
Degré d’un graphe non orienté : degré maximum de tout ses sommets.
Graphe k-régulier : graphe où tous les sommets ont le même degré.\

Démontrer que la somme des degrés des sommets d’un graphe est égale à 2 fois le nombre d’arrêtes.

Chaque arête ajoute 1 degré aux sommets qu'elle relie => chaque arête ajoute 2 degrés (un pour chaque sommet).
Donc, la somme des degrés est bien égale au double du nombre d'arêtes.

Démontrer qu'un graphe simple a un nombre pair de sommets de degré impair.

La somme des degrés des sommets d’un graphe est égale à 2 |E|, donc elle est paire. Or, la somme d’un nombre impair de degrés impairs est elle-même impaire. En l’ajoutant aux degrés pairs (qui donnent une somme paire), on obtiendrait une somme totale impaire, ce qui est impossible. Ainsi, le nombre de sommets de degré impair doit être pair.

Démontrer que dans une assemblée de n personnes, il y a toujours au moins 2 personnes qui ont le même nombre d’amis présents.

Dans un graphe simple avec n sommets, le degré d'un sommet peut varier entre 0 (aucun ami) et n-1 (ami avec tous les autres sommets).
Si quelqu'un a 0 ami, alors cette personne n'est amie avec personne.
Si quelqu'un a n-1 ami, alors cette personne est amie avec tout le monde.
Si une personne est amie avec tout le monde alors il n'y a personne sans amis et le contraire est aussi viable. Alors aucune personne ne peut avoir n-1 amis ce qui nous donne une contradiction :
Impossible que toutes les personnes aient un nombre unique d'amis.
Au moins 2 personnes doivent partager le même nombre d'amis.