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:
Stupanj nekog čvora je broj bridova koji ga dodiruju.
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.
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.
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.
DA ako ulaz zadovoljava uvjet zadatka, ako nije onda ispišite NE.
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.
8 1 2 1 3 2 3 2 4 1 4 3 4 3 5 5 4
DA
Primjer izgleda ovako:
Jedan mogući put je: 1 - 3 - 5 - 4 -3 - 2 - 1- 4 -2.
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?
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License