Kuvaajan kävely

On olemassa lukuisia ongelmia vuonna graafiteoria jotka käsittelevät liikkumisesta kuvaajat . Reunojen läpi kulkevien ongelmien ja solmujen läpi kulkevien ongelmien välillä tehdään ero . Tärkeimmät tämän tyyppiset ongelmat on esitetty lyhyesti alla.

Euler-ympyrän ongelma

Euler-sykliongelma tutkii kuvaajan reunojen läpäisevyyttä. Kysymys kuuluu, onko olemassa sykli, joka kulkee kaavion kaikkien reunojen läpi täsmälleen kerran. On huomattava, että se on välttämätöntä ja riittävää, jos graafilla on vierekkäinen ja kaikilla suorilla asteilla olevilla solmuilla . Tämä ominaisuus voidaan helposti tarkistaa lineaarisessa ajassa käyttämällä syvyyshakua . On myös mahdollista löytää tällainen sykli (jos sellainen on) lineaarisella ajoajalla.

Postimiehen ongelma

Kiinan Postman ongelma , pyytää lyhin reitti kaikkien reunat reuna-painotettu kuvaaja . Kaavioille, joissa on Euler-ympyrä, tämä reitti vastaa ilmeisesti Euler-ympyrää. Muissa kaavioissa reunat on välttämättä ajettava useita kertoja. Näiden reunojen pituus on minimoitava. Tätä varten riittää löytää pienin täydellinen osatekijä on matkan kuvaaja kaikki solmut on pariton astetta. Tämä on mahdollista polynomiajassa. Tämän pariliitoksen reunojen mukaan liitetyt reunat on kopioitava alkuperäiseen kaavioon. Tämä luo kaavion, jolla on Euler-ympyrä. Nyt riittää löytää Euler-ympyrä.

Hamilton-syklin ongelma

Hamilton-sykliongelma tutkii kuvaajan solmujen läpäisevyyttä. Kysymys on, onko olemassa ympyrä, joka sisältää kaavion jokaisen solmun. Ongelma on NP-täydellinen . Joitakin riittäviä ja välttämättömiä ehtoja Hamilton-syklin olemassaololle tiedetään, joten on mahdollista tarkistaa tehokkaasti joillekin kaavioille, onko niillä Hamilton-sykli.

Myyjäongelma

Matkustaa myyjä ongelma pyytää lyhyimmän edestakaisen yli kaikki solmut reuna-painotettu täydellinen kuvaaja. Tämä ongelma on myös NP-täydellinen. Joidenkin kohtuullisten oletusten avulla ( kolmion eriarvoisuus ) on mahdollista käsitellä ongelmaa ainakin suunnilleen .