Eulerova staza
Eulerova staza grafa je staza (put) koja prolazi svakim bridom od točno jednom.
Eulerova tura je zatvorena Eulerova staza. Dakle, to je zatvorena staza koja prolazi svakim bridom točno jedanput.
Graf je Eulerov ako ima Eulerovu turu, odnosno ako vrijedi:
- Neprazan povezan graf G je Eulerov ako i samo ako su mu svi vrhovi parnog stupnja.
- Povezani graf G ima Eulerovu stazu ako i samo ako ima najviše dva vrha neparnog stupnja.
Stupanj nekog čvora je broj bridova koji ga dodiruju.
Primjer
Zadan je graf koji se nalazi na gornjoj slici. Ima li on Eulerovu turu? Nema jer ne zadovoljava svojstva koja su potrebna da graf postane Eulerov.
To znači da nisu svi vrhovi parnoga stupnja, primjerice (6 i 4), ali i sadrži više od dva čvora koja imaju neparan stuapnj, a to su redom: 2,4,5 i 6.
Zadaci
Ralica
Kao pripremu za zimu Grad Zagreb gradi mrežu cesta na način da ih ralica sve može proći na način da niti jednu ulicu ne prelazi više od jednoga puta. Vama je zadan broj točaka, te koja je točka povezana s kojom(riječ je naravno o dvosmjernim ulicama). I iz tih podatak trebate ispisati je li sustav cesta napravljen način kako traži gornji uvjet zadatka,tj. da ralica može proći sve ulice na način da svaku prođe samo jednom.
Ulaz
Broj N – broj točaka i u sljedećih N (N>0 i N < 1000) ulaza brojeve A i B koji označuju da su točke A i B povezane.
Izlaz
DA ako ulaz zadovoljava uvjet zadatka, ako nije onda ispišite NE.
Napomena
U test podacima neće biti slučaj da će se ulice ponavljati npr. da se unese prvo 3 5 pa onda kasnije 5 3.
Primjer
8 1 2 1 3 2 3 2 4 1 4 3 4 3 5 5 4
DAObjašnjenje
Primjer izgleda ovako:
Jedan mogući put je: 1 - 3 - 5 - 4 -3 - 2 - 1- 4 -2.
Kosa projekcija
Može li se nacrtati kosa projekcija kocke (prikazana na slici) u jednom potezu?
Dana su tri sukladna kvadrata u međusobnom položaju prikazanom na slici. Možemo li ovu sličicu nacrtati u jednom potezu?
Zadaci
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License