Википедија

Teorema četiri boje — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 17:
[[File:4CT Inadequacy Example.svg|center]]
 
Na ovoj mapi, dve regiona sa oznakom ''A'' pripadaju istoj zemlji. Ako bi se želelo da ti regioni dobiju istu boju, tada bi bilo potrebno pet boja, jer su dva ''A'' regiona zajedno susedna sa četiri druga regiona, svaki od kojih pripada svim ostalim. Slična konstrukcija se takođe primenjuje ako se za sva vodena tela koristi jedna boja, kao što je to uobičajeno na stvarnim mapama. Za mape u kojima više zemalja može imati više nepovezanih regija, moguće je da će biti potrebno šest ili više boja.
In this map, the two regions labeled ''A'' belong to the same country. If we wanted those regions to receive the same color, then five colors would be required, since the two ''A'' regions together are adjacent to four other regions, each of which is adjacent to all the others. A similar construction also applies if a single color is used for all bodies of water, as is usual on real maps. For maps in which more than one country may have multiple disconnected regions, six or more colors might be required.
 
[[File:Four Colour Planar Graph.svg|thumb|right|AMapa mapsa withčetiri four regionsregiona, and thei correspondingkorespondirajućim planarplanarnim graphgrafom withsa fourčetiri verticesvrha.]]
Jednostavnija formulacija teoreme koristi [[graph theory|teoriju grafova]]. Skup regiona mape se može apstraktnije predstaviti kao [[undirected graph|neusmereni graf]] koji ima [[vertex (graph theory)|vrh]] za svaki region i [[Glossary of graph theory terms|ivicu]] za svaki par regiona koji imaju granični segment. Ovaj graf je planaran: on se može nacrtati u ravni bez ukrštanja postavljanjem svakog vrha na proizvoljno odabranu lokaciju unutar regije kojoj pripada, i crtanjem ivica kao krivih bez ukrštanja, koje vode od vrha jednog regiona, preko zajedničkog graničnog segmenta, do vrha susednog regiona. Suprotno tome, bilo koji planarni graf može se formirati iz mape na ovaj način. U grafno-teorijskoj terminologiji, teorema četiri boje navodi da se vrhovi svakog planarnog grafa mogu obojiti sa najviše četiri boje tako da nijedan par susednih vrhova ne dobije istu boju ili ukratko:
A simpler statement of the theorem uses [[graph theory]]. The set of regions of a map can be represented more abstractly as an [[undirected graph]] that has a [[vertex (graph theory)|vertex]] for each region and an [[edge (graph theory)|edge]] for every pair of regions that share a boundary segment. This graph is [[planar graph|planar]]: it can be drawn in the plane without crossings by placing each vertex at an arbitrarily chosen location within the region to which it corresponds, and by drawing the edges as curves without crossings that lead from one region's vertex, across a shared boundary segment, to an adjacent region's vertex. Conversely any planar graph can be formed from a map in this way. In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short:
:Every planarSvaki graphplanarni isgraf je [[GraphБојење coloringграфова|four-colorablečetvorobojan]].<ref>{{harvtxt|Thomas|1998|p=849}}; </ref><ref>{{harvtxt|Wilson|2014}}).</ref>▼
 
▲:Every planar graph is [[Graph coloring|four-colorable]].<ref>{{harvtxt|Thomas|1998|p=849}}; {{harvtxt|Wilson|2014}}).</ref>
 
== Reference ==
Преузето из „https://sr.wikipedia.org/wiki/Teorema_četiri_boje”