Cycles et facteurs dans les graphes : application de la théorie des graphes aux réseaux de Pétri
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis is constituted by several chapters. The first one deals with the existence of certain cycles in graphs of large degree. It gives sufficient conditions for the existence of cycles of length greater than a given number m, of dominating cycles, of circuits containing a set of s vertices and of length at most 2s. The second one gives sufficient conditions for the existence of f-factors in graphs, with conditions of independence number and connectivity, of number of edges, and also by assuming the existence of f-factors in some subgraphs. The third deals with covering of edges and vertices of a graph by cycles, the sum of the length of the cycles being minimal. Finally, the fourth is an application of the graph theory to Petri nets. It gives sufficient conditions for liveness on a class of nets.
Abstract FR:
Cette thèse se compose de plusieurs chapitres/ le premier porte sur l’existence de certains cycles dans des graphes de grand degré. Il donne des résultats de conditions suffisantes d’existence du cycle de longueur supérieure à un nombre m fixé, de cycle dominant, de circuit contenant s sommets et de longueur au plus 2s. Le second porte sur des conditions suffisantes d’existence de f-facteurs de graphes, avec condition de stabilité et connexité, d’une part, nombre d’arcs, d’autre part, existence de f-facteurs dans certains sous-graphes, enfin. Le troisième porte sur les couvertures des arêtes et des sommets d’un graphe par une famille de cycles de longueur totale minimale. Enfin le quatrième traite d’une application de la théorie des graphes à la théorie des réseaux de Petri. Il donne des conditions suffisantes de vivacité pour certains réseaux.