| dbo:abstract
|
- In graph theory, the Graham–Pollak theorem states that the edges of an -vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry. The theorem has since become well known and repeatedly studied and generalized in graph theory, in part because of its elegant proof using techniques from algebraic graph theory. More strongly, write that all proofs are somehow based on linear algebra: "no combinatorial proof for this result is known". (en)
- En théorie des graphes, le théorème de Graham-Pollak affirme que les arêtes d'un graphe complet à sommets ne peut être partitionné en moins de graphes bipartis complets. Il a d'abord été publié par Ronald Graham et Henry O. Pollak dans deux articles en 1971 et 1972, dans le cadre d'une application aux circuits de commutation téléphonique. Le théorème est depuis devenu bien connu et a été étudié et généralisé à plusieurs reprises en théorie des graphes, en partie à cause de sa preuve élégante utilisant des techniques de la théorie algébrique des graphes. Plus précisément, Aigner & Ziegler écrivent que toutes les preuves sont basées d'une manière ou d'une autre sur l'algèbre linéaire : « aucune preuve combinatoire pour ce résultat n'est connue ». (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10285 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In graph theory, the Graham–Pollak theorem states that the edges of an -vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry. (en)
- En théorie des graphes, le théorème de Graham-Pollak affirme que les arêtes d'un graphe complet à sommets ne peut être partitionné en moins de graphes bipartis complets. Il a d'abord été publié par Ronald Graham et Henry O. Pollak dans deux articles en 1971 et 1972, dans le cadre d'une application aux circuits de commutation téléphonique. (fr)
|
| rdfs:label
|
- Graham–Pollak theorem (en)
- Théorème de Graham-Pollak (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
