Séparateurs minimaux, Disjoints internes, Théorème de Menger, Chemins orientés, Forêt maximale, Chemins a trois blocs, Ensembles stables

Cette thèse est divisée en deux parties principales: la partie I se concentre sur le théorème de Menger, qui dans sa version la plus connue, énonce que la taille minimum d'un sous-ensemble de sommets separant deux sommets non adjacents est égale au nombre maximum de chemins internement disjoints reliant ces deux sommets. Notant que deux chemins qui ont les mêmes extrémités sont intérieurement disjoints si et seulement s'ils ne partagent aucun sommet à l'exception de leurs extrémités. Nous présenterons ce théorème sous ses deux formes distinctes, et fournirons également un compte rendu de certaines des preuves qui ont été données pour cela, et nous expliquerons comment le théorème de Menger nous permet de prouver un nouveau théorème concernant le séparateur minimal des graphes entre n'importe quel deux sommets non adjacents. Notre nouvelle contribution est de montrer que ces deux théorèmes sont équivalentes, ainsi que de fournir des preuves indépendantes pour la seconde; En conséquence, la théorème de Menger est désormais étayée par de nouveau preuve, ce qui la rend encore plus fascinante. Cette introduction ne résume pas la première partie, mais nous allons plutôt examiner de plus près le théorème de Hall et montrer comment nous pouvons générer une opportunité pour deux nouvelles preuves à l'appui, dont l'une est basée sur le théorème de Menger. La partie II étudie la présence de chemins orientés dans les digraphes avec un nombre chromatiques de k. Notre objectif central sera de découvrir un entier k dans lequel chaque digraphe avec un nombre chromatiques k a un sous-digraphe comme copie d'un chemin orienté donné avec trois blocs ou avec quatre blocs.