Attributes | Values |
---|
type
| |
Thesis advisor
| |
Author
| |
alternative label
| - COLOURINGS AND ORIENTATIONS OF GRAPHS
|
dc:subject
| - Thèses et écrits académiques
- SCIENCES ET TECHNIQUES COMMUNES : MATHEMATIQUES
- Coloriage de graphes
- Graphes orientés
- THEORIE GRAPHE/GRAPHE ORIENTE/COLORATION GRAPHE/GRAPHE CHROMATIQUE/CHEMIN GRAPHE
- GRAPH THEORY/DIRECTED GRAPH/GRAPH COLOURING/CHROMATIC GRAPH/GRAPH PATH
|
preferred label
| - Colorations et orientations des graphes
|
Language
| |
Subject
| |
dc:title
| - Colorations et orientations des graphes
|
Degree granting institution
| |
note
| - LA THESE EST CONSTITUEE DE DEUX PARTIES FONCTIONS ET LINE DIGRAPHES ET CHEMINS DANS DES GRAPHES ORIENTES N-CHROMATIQUES. DANS LA PREMIERE PARTIE, NOUS DONNONS LA DEFINITION DES LINE DIGRAPHES. NOUS DISCUTONS LE PROBLEME DE LA RECONNAISSANCE DES GRAPHES SOUSJACENTS DES LINE DIGRAPHES. CHVATAL ET EBENEGGER ONT DEMONTRE QUE CE PROBLEME EST NP-COMPLET. NOUS REMARQUONS QUE LEUR PREUVE SUFFIT POUR DEMONTRER QUE LE PROBLEME RESTE NP-COMPLET SI ON SE LIMITE AU LINE DIGRAPHES L(H), OU H EST UN DIGRAPHE DANS LEQUEL TOUT SOMMET A UN DEGREE INTERIEUR OU EXTERIEUR AU PLUS UN. NOUS CARACTERISONS ENSUITE CES GRAPHES EN RAJOUTANT UNE CONDITION SUPPLEMENTAIRE. PLUSIEURS APPLICATIONS SUR DES STRUCTURES DES FONCTIONS SONT DONNEES ENSUITE. DANS LA DEUXIEME PARTIE, NOUS PARTONS DE LA QUESTION SUIVANTE: SOIT D UNE ORIENTATION D'UN GRAPHE N-CHROMATIQUE. QUELS SONT LES CHEMINS ORIENTES QU'ON EST SUR DE TROUVER DANS D COMME SOUS-DIGRAPHES. NOUS TRAITONS DEUX TYPES PARTICULIERS DE CHEMINS: 1. LES CHEMINS CONSTITUES PAR DEUX BLOCS 2. LES CHEMINS ANTIDIRECTES
|
dc:type
| |
http://iflastandar...bd/elements/P1001
| |
rdaw:P10219
| |
has content type
| |
is primary topic
of | |
is rdam:P30135
of | |