Základní informace o projektu

Fórum o projektu

Moderátoři: petnek, nenym, Zelvuska

Odpovědět
Zpráva
Autor
Uživatelský avatar
forest
Admin webu a fóra CNT
Admin webu a fóra CNT
Příspěvky: 17733
Registrován: pát 27 říj, 2006 10:19
rok narození: 03 bře 1977
ID CNT statistics: 71
Bydliště: Újezd u Brna

Základní informace o projektu

#1 Příspěvek od forest » pát 20 dub, 2007 08:12

Základní info o projektu:
V projektu jde o hledání ideálních vykreslení úplných grafů s ,,n,, počtem uzlů, s minimálním počtem křížení hran.

Graf je obrazec, jen z bodů a z linií, které tyto body spolu spojí. Body se nazývají ,,uzly,, a linie ,,hrany,,. Mnoho otázek ve výpočtové a kombinatorické geometrii je založena na konečných souborech bodů (uzlů) v euklidovském prostoru. Euklidovský prostor je prostor se skalárním součinem (reálný unitární prostor), který má konečnou dimenzi a značí se En. Rozšířením euklidovského prostoru En lze získat n-rozměrný komplexní prostor Kn.

Grafy s jedním, dvěma nebo třemi uzly nemají žádné zásadní průsečíky. Také grafy se 4 uzly mohou být uspořádány tak, aby nedocházelo ke křížení uzlů. Poprvé u grafu s pěti uzly je nejméně jedno takové křížení. S výším počtem uzlů se zvedá i počet křížení. Například u n=6 dochází ke 3 křížením, u n=7 k 9, n=8 uzlů k 19 a u n=9 k 36.
Pro větší bodové množiny je velmi těžké určit nejlepší uspořádání. Hlavní důvod je že počet kombinací různých možností umístění jednotlivých uzlů rostou exponenciálně. Například již pro n=11 to je 2 334 512 907 různých kombinací. Hodnoty pro n=11 byly nalezeny až v roce 2004.

V roce 2004 vznikl právě projekt The Rectilinear Crossing Number Project za účelem hledání co nejmenšího počtu křížení u jednotlivých počtů uzlů. Do konce ledna roku 2007 bylo takto prozkoumáno již n=12 -18 u kterého již dochází k nejméně k 1029 křížení uzlů.

Stránky projektu: http://dist.ist.tugraz.at/cape5/

Ostatní důležité odkazy najdete jako vždy v této sekci na našem webu.

Odpovědět

Zpět na „Rectilinear Crossing Number“