Théorie des graphes

vignette|Un tracé de graphe. La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets. Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non symétriques (les graphes sont alors dits orientés) et sont alors appelées des flèches ou des arcs. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.) et dans bien d'autres domaines (par exemple génétique) tant le concept de graphe, à peu près équivalent à celui de relation binaire (à ne pas confondre donc avec graphe d'une fonction), est général. De grands théorèmes difficiles, comme le théorème des quatre couleurs, le théorème des graphes parfaits, ou encore le théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la conjecture de Hadwiger, en font une branche vivace des mathématiques discrètes. Lexique de la théorie des graphes vignette|Un graphe orienté avec trois sommets et quatre arcs. Un graphe est un couple comprenant deux ensembles : sommets ; arêtes, chacune étant associée à un couple ou une paire de sommets (u, v ∈ V). Il y a plusieurs principaux types de graphes : Dans un graphe non orienté, les arêtes n'ont pas d'orientation et sont donc associées à une paire . Dans un graphe orienté, les arêtes sont appelées arcs et ont une orientation de vers ; elles sont ainsi associées au couple . Un graphe mixte comporte à la fois des arêtes et des arcs, on le définit alors plutôt comme le triplet . Un graphe simple est un graphe ne comportant ni boucles ni multi-arêtes, c'est-à-dire qu'aucun sommet n'est connecté à lui-même, et entre deux sommets il n'existe qu'une seule arête.

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Non-planarity of Markoff graphs mod p

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Non-planarity of Markoff graphs mod p