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:

  1. Neprazan povezan graf G je Eulerov ako i samo ako su mu svi vrhovi parnog stupnja.
  2. 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
ulaz
8
1 2
1 3
2 3
2 4
1 4
3 4
3 5
5 4
izlaz
DA
Objaš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

Play on Words

Islands and Hotel Chains

The Necklace

The Postal Worker Rings Once

John's trip

Catenyms

Snow Clearing

© 2014. Lovro Sindičić Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License