Dosiero:Grötzsch_graph.svg
From Wikipedia, the free encyclopedia
Bildo en pli alta difino (SVG-dosiero, 480 × 460 rastrumeroj, grandeco de dosiero: 8 KB)
Jen dosiero de la Wikimedia-Komunejo. La priskribo en ties priskriba paĝo estas montrata suben.
|
Resumo
Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every there is a graph with chromatic number k that contains no triangle subgraphs, that is, whose maximal clique size is just 2. (This was also proved by A. A. Zykov, Mat. Zb. 24, (1949), 2, 163-183 (in Russian) and by "Blanche Descartes" (W. T. Tutte) Amer. Math. Monthly 61, (1954) p. 352.) The chromatic number of this graph is 4.
A simple construction of triangle-free graphs of any chromatic number is this. Start with a -chromatic graph G with no triangle. Take copies of G. Form all sets consisting of 1 node from each copy. Connect the nodes in each of these sets to a new node. The resulting graph is triangle-free and -chromatic.
If you can make the image look better, by all means do so.
Permesiloj:
Public domainPublic domainfalsefalse |
Ĉi tiu verko estis liberigita kiel publika havaĵo de ties aŭtoro, Bkell. Tio aplikatas tutmonde. En iuj landoj tio povas esti laŭleĝe neebla; en tiu okazo: |
Originala alŝutada protokolo
date/time | username | resolution | size | edit summary | |
---|---|---|---|---|---|
09:37, 17 December 2006 | User:Booyabazooka | <a href="http://upload.wikimedia.org/wikipedia/commons/5/5e/Fourth_Mycielski_graph.svg"><img alt="Thumbnail for version as of 09:37, 17 December 2006" src="http://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Fourth_Mycielski_graph.svg/120px-Fourth_Mycielski_graph.svg.png" width="120" height="115" border="0" /></a> | 480×460 | 8 KB | Prettier version requested... how's this? |
10:33, 3 July 2006 | User:Bkell | <a href="http://upload.wikimedia.org/wikipedia/commons/archive/5/5e/20061217093723%21Fourth_Mycielski_graph.svg"><img alt="Thumbnail for version as of 10:33, 3 July 2006" src="http://upload.wikimedia.org/wikipedia/commons/thumb/archive/5/5e/20061217093723%21Fourth_Mycielski_graph.svg/120px-Fourth_Mycielski_graph.svg.png" width="120" height="120" border="0" /></a> | 700×700 | 6 KB | Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every <math>k\ge1</math> there is a graph with chromatic number ''k'' that contains no triangle subgraphs, that is, whose maximal clique size is just 2. The chromati |
Eroj prezentitaj en ĉi tiu dosiero
montras
Dosierhistorio
Alklaku iun daton kaj horon por vidi kiel la dosiero tiam aspektis.
Dato/Horo | Bildeto | Grandecoj | Uzanto | Komento | |
---|---|---|---|---|---|
nun | 18:14, 21 nov. 2008 | 480 × 460 (8 KB) | BetacommandBot | move approved by: User:Deadstar This image was moved from Image:Fourth Mycielski graph.svg == Summary == Very hastily drawn image of the fourth Mycielski graph. Mycielski proved in 1955 that for every <math>k\ge1</math> there is a graph with c |
Dosiera uzado
La jenaj paĝoj ligas al ĉi tiu dosiero:
Suma uzado de la dosiero
La jenaj aliaj vikioj utiligas ĉi tiun dosieron:
- Uzado en en.wikipedia.org
- Uzado en fr.wikipedia.org
- Uzado en hu.wikipedia.org
- Uzado en pl.wikipedia.org
- Graf pełny
- Teoria grafów
- Kod Graya
- Graf (matematyka)
- Drzewo (matematyka)
- Las (matematyka)
- Podgraf
- Twierdzenie o czterech barwach
- Drzewo rozpinające
- Minimalne drzewo rozpinające
- Algorytm Prima
- Algorytm Kruskala
- Cykl Hamiltona
- Cykl Eulera
- Graf skierowany
- Klika (teoria grafów)
- Algorytm Dijkstry
- Graf planarny
- Problem komiwojażera
- Twierdzenie Kuratowskiego
- Homeomorfizm grafów
- Problem najkrótszej ścieżki
- Algorytm Bellmana-Forda
- Algorytm Floyda-Warshalla
- Algorytm najbliższego sąsiada
- Most (teoria grafów)
- Graf spójny
- Punkt artykulacji
- Kolorowanie grafu
- Liczba chromatyczna
- Graf pierwotny
- Klasa grafów
- Graf acykliczny
- Graf prosty
- Pętla (teoria grafów)
- Rdzeń grafu
Vidi plian ĝeneralan uzadon de ĉi tiu dosiero.