[Mat08] Optimalizálás szeminárium

[Csilla Majoros]

*MeghĂ­vĂł*

Szeretettel várunk minden kedves érdeklődőt a BME
OptimalizĂĄlĂĄs SzeminĂĄriumĂĄn!


Az előadás részletei:

*februĂĄr 26. (csĂźtĂśrtĂśk), 14.15, H306*


*Hujter MihĂĄly (BME):*GrĂĄfok szĂ­nezĂŠse ĂŠs jĂłl karakterizĂĄlĂĄs

*Absztrakt:*
GrĂĄfokat helyesen szĂ­nezni adott szĂĄmĂş szĂ­nnel ĂĄltalĂĄban nem kĂśnnyĹą
feladat. Ha sikerrel jĂĄrunk, az eredmĂŠny ĂśnmagĂĄĂŠrt beszĂŠl: kĂśnnyen
ellenőrizhető, hogy helyes a színezés. Ha viszont nem sikerül, általában
sokkal nehezebb igazolni, hogy nincs megfelelő színezés. Öt és fél évtizede
Hajós György megmutatta, hogy adott k-ra a k színnel nem színezhető
grĂĄfokat hogyan lehet felĂŠpĂ­teni nĂŠgyfĂŠle operĂĄciĂł vĂĄltogatĂĄsa rĂŠvĂŠn,
kiindulva a k+1 pontĂş teljes grĂĄfbĂłl: pont hozzĂĄadĂĄsa / ĂŠl hozzĂĄadĂĄsa /
duplikĂĄtum pontok kĂśzĂźl az egyik elhagyĂĄsa / kĂŠt grĂĄfnak egy kĂśzĂśs pont
mentén történő összekovácsolása egy-egy régi él elhagyásával és egy új él
behĂşzĂĄsĂĄval.
Gyakorlati alkalmazhatóságtól indíttatva az előadásban azt a
problĂŠmavĂĄltozatot vizsgĂĄljuk, amikor mĂĄr egy rĂŠszben kiszĂ­nezett grĂĄf
helyes teljes szĂ­nezĂŠsĂŠnek lehetetlensĂŠgĂŠt akarjuk konstruktĂ­van
megmutatni. A mĂĄr definiĂĄlt mĹąveletekhez hĂĄrom Ăşjabbat adunk: a fenti
módszerrel legyártott gráfokban egy teljes részgráf pontjait különböző
szĂ­nekkel kiszĂ­nezzĂźk (de ezt csak egyszer tehetjĂźk meg) / szĂ­nezett
pontokbĂłl duplikĂĄtumkĂŠnt azonos szĂ­nĹą pontokat gyĂĄrtunk / szĂ­nezett pontok
kĂśzĂśtti ĂŠleket tĂśrlĂźnk.
Bizonyítjuk, hogy ezekkel a műveletekkel olyan és csak olyan előszínezett
grĂĄfokhoz jutunk, melyek helyes teljes szĂ­nezĂŠse k szĂ­nnel lehetetlen.
A gyakorlati alkalmazĂĄsok szempontjĂĄbĂłl fontos speciĂĄlis esetekre kĂźlĂśn
figyelmet fordĂ­tunk.


A *következő alkalmak* részleteit itt találhatják:

http://www.math.bme.hu/diffe/szeminarium/opt.shtml


Üdvözlettel,

Majoros Csilla
--------- következő rész ---------
Egy csatolt HTML ĂĄllomĂĄny ĂĄt lett konvertĂĄlva...
URL: http://lists.math.bme.hu/pipermail/mat08/attachments/20150224/491e5963/attachment.htm