     
P 50 (2022/2023) 3 5
Semaforji in barvanje grafov
S Č
Namen cestnega omrežja je, da lahko s potjo po-
vežemo poljubni dve lokaciji. To neizbežno vodi v
križišča, kjer se poti vozil, namenjenih v različne
smeri, morajo sekati. Potrebi po križiščih se lahko
izognemo z izrabo tretje dimenzije – z nadvozi. Te
uporabimo predvsem pri avtocestah, kjer je pre-
točnost brez ustavljanja poglavitnega pomena. Pri
drugih cestah, predvsem v naseljih, je to predrago
in prostorsko preveč potratno. Tam izkoriščamo
nivojska križišča – križišča brez nadvozov in pod-
vozov, kjer lahko varnost zagotovimo s predno-
stnimi pravili, ki jih morajo vozniki dobro poznati,
ali pa s pomočjo semaforja, posebej pri križiščih z
visoko pretočnostjo.
Vozniki z vsake ceste v križišču lahko zavijejo v
katerokoli smer, česar v nivojskem križišču ne mo-
remo zagotoviti sočasno brez sekanja. Semafor pro-
blem križanja poti reši tako, da poti namesto v pro-
storu razporedi v času. V matematični idealizaciji
vsaka stopnja semaforja dovoljuje le poti, ki se med
seboj ne križajo. V vseh stopnjah semaforja, preden
se cikel ponovi, morajo priti na vrsto vsi, ne glede na
to, kam zavijajo.
Kot matematiki se lahko vprašamo, kolikšno je
najmanjše število stopenj, ki jih potrebujemo za ne-
ko križišče, in koliko različnih kombinacij semafor-
nih stopenj je mogočih. Pred matematično obrav-
navo moramo problem preoblikovati v bolj čisto in
pregledno obliko. Pri tem so bolj kot začetne in kon-
čne točke poti pomembne poti same.
Za vsako križišče moramo najprej poiskati vse po-
ti. Pri tem bomo izpustili zavijanje v desno, saj je to
SLIKA 1.
Grafe in zemljevide barvamo tako, da so sosedi razlǐcnih barv.
Levo: neveljavno barvanje. Desno: veljavno barvanje.
vedno mogoče vsaj takrat, ko je omogočen tudi pro-
met naravnost, ter na splošnem vedno, kadar cesta
na desni nima drugih »pritokov«. Za desne zavoje bo
zato v semafornem ciklu vedno prostor, ko določimo
vse drugo. V nekaterih križiščih ima desni zavoj svoj
pas, ki ni odvisen od semaforja. V ZDA je previdno
zavijanje v desno dovoljeno celo pri rdeči luči, kar
smo v preteklem letu na nekaterih izbranih križiščih
dovolili tudi v Sloveniji. Prav tako bomo prepovedali
polkrožno obračanje.
Vozniki vemo, da je največji izziv zavijanje v levo,
saj s tem sekamo pot nasproti vozečim vozilom. V
praksi semaforji pogosto nimajo posebne stopnje za
zavijanje v levo, ampak vozniki čakajo v sredini kri-
žišča, da se jim pot sprosti. Za našo analizo bo bolj
ugodno, da ta primer idealiziramo kot sosledje dveh
stopenj – prvo za vožnjo naravnost in drugo za zavi-
janje v levo. Tako bodo vse naše semaforne stopnje
resnično brez sekanja poti.
Naslednji korak je, da poiščemo vse pare poti, ki
se križajo. Če se poti križata, vemo, da se morata po-
javiti v različnih stopnjah semafornega cikla. Mno-
žico poti in križajočih se parov bomo predstavili ma-
tematično kot graf – množico vozlišč (poti) in pove-
     
P 50 (2022/2023) 36
A
B
C
A
B
C
SLIKA 2.
Križišče treh cest in pripadajoči graf. Puščice istih barv pome-
nijo poti, ki imajo hkrati zeleno luč. Te barve ustrezajo barvam
vozlišč grafa.
zav (prepovedanih parov poti). Vsako križišče lahko
predstavimo torej kot neusmerjen graf, pri čemer je
pogoj, da vozlišča, ki so med seboj povezana, ne
smejo biti v isti stopnji semafornega cikla. To pre-
poznamo kot znano vprašanje iz teorije grafov: z
najmanj koliko barvami lahko pobarvamo graf (ali
zemljevid), da sta dve sosednji vozlišči (državi) ve-
dno različnih barv (glej sliko 1). Še več, vsako raz-
lično barvanje grafa pripada drugačnemu semafor-
nemu ciklu, permutacija barv pa ustreza menjavi vr-
stnega reda stopenj cikla.
Pri določanju, katere poti se sekajo, moramo spre-
jeti še nekaj odločitev. Kadar se poti križata v sre-
dini križišča, gre vsekakor za prepovedano kombi-
nacijo. Če se sekata na začetku, pa to pomeni za-
vijanje z iste vstopne ceste. To ne predstavlja ne-
varnosti za trk, je pa problematično, če imata dva
zaporedna avtomobila namen zavijati v smereh, ki
nimata hkrati zelene luči. V teh primerih moramo
imeti več vstopnih pasov in torej širšo cesto. Če se
poti sekata v končni točki, imamo drugačen problem
– če v isti izhodni pas hkrati vstopajo vozila z različ-
nih smeri, imamo nevarnost trka. Razrešitev te ne-
varnosti lahko prepustimo previdnosti voznikov, ali
pa jim dodelimo več izstopnih pasov, kar spet zah-
teva širšo cesto. Ta presečišča lahko tudi enostavno
prepovemo in dobimo bolj stroge pogoje za veljavne
semaforne stopnje.
Najenostavnejši primer je križišče treh cest na sli-
ki 2, katerega pripadajoči graf je kar trikotnik. Tega
lahko pobarvamo le na en način, in to s tremi bar-
vami. Raje se posvetimo bolj zanimivemu primeru
križišča štirih cest, najprej za primer, ko prepovemo
sekanje v končni točki. Pripadajoči graf lahko po-
barvamo s štirimi barvami, torej potrebujemo štiri
stopnje semafornega cikla. Slika 3 prikazuje vse tri
možne semaforne cikle s pripadajočimi pobarvanimi
grafi. Semaforni cikel α je najbolj tipičen: najprej
imamo vožnjo naravnost v smereh vzhod-zahod, sle-
di zavijanje v levo z istih cest, potem pa isto pono-
vimo še za smeri sever-jug. Ta semaforni cikel zah-
A
C
B
D
C
A
D
B
A
D
C
B
A
D
C
B
A
C
B
D
C
A
D
B
A
D
C
B
A
C
B
D
C
A
D
B
SLIKA 3.
Graf za križišče štirih cest lahko po-
barvamo na tri načine. Vozlišča is-
tih barv predstavljajo hkratno zeleno
luč, in na grafu niso povezana.
     
P 50 (2022/2023) 3 7
A
C
B
D
C
A
D
B
A
C
B
D
C
A
D
B
A
D
C
B
A
D
C
B
SLIKA 4.
Križišče s štirimi cestami z dovoljenim hkratnim zavijanjem v
isto smer.
teva ločen pas za zavijanje v levo. Pri manjših križi-
ščih to ni rešeno z ločeno stopnjo semaforja, ampak
vozniki le počakajo v križišču. Cikel γ je najeno-
stavnejši, saj za vsako cesto odpremo zavijanje v vse
smeri, medtem ko na preostalih treh cestah čakajo.
Ta ne zahteva niti dodatnih pasov niti čakanja v kri-
žišču, je pa redko v rabi, saj je v praksi ena cesta
prednostna in je zavijanja v levo malo. V teh pri-
merih ima cikel α večji pretok, sploh če je dovolj
prostora za čakanje v sredini križišča. Cikel β je
kombinacija obeh ciklov – naravnost in levo v sme-
reh vzhod-zahod, posamični cesti v smereh jug in
sever.
Če dovolimo tudi sekanje v končni točki, dobimo
še dva dodatna cikla, prikazana na sliki 4. V primeru
δ pride do hkratnega zavijanja na cesti sever in jug,
v primeru ǫ pa v vse štiri izhodne ceste. Na grafu so
z rumeno označene povezave, ki pripadajo sekanju
v končni točki.
Še zanimivejši problem je križišče običajne ceste
in avtocestnih priključkov, kjer je ena izmed eno-
smernih cest samo vstopna, druga pa samo izstopna.
V tem primeru je možnih poti pet, dobljeni graf, ki
je kar cikličen, pa lahko pobarvamo z le tremi bar-
vami, in to na štiri možne načine, prikazane na sliki
5. Opazimo pa, da se prva dva načina razlikujeta le
v barvi C ↑ – to pomeni, da lahko ta dva cikla zdru-
žimo in pustimo zeleno luč C ↑ v dveh stopnjah ci-
kla, in povečamo pretočnost križišča. Podobno velja
za preostala dva načina – v tem primeru smer A ↑
lahko pobarvamo z dvema barvama, ne da bi prišlo
do presečišč. V resnici imamo torej le dve možnosti.
Kako pa računsko, brez risanja, ugotovimo, ali se
dve poti sekata? V ta namen si bomo mislili, da vse
vstopne in izstopne točke v križišče ležijo na kro-
žnici in jih oštevilčili s števili od 0 do n − 1 v smeri
urnega kazalca. aZ in aK naj bosta začetni in končni
indeks prve poti, bZ in bK pa začetni in končni in-
deks druge. Zdaj potujmo zgolj v smeri urnega ka-
zalca, in poskusimo na poti od aZ do aK obiskati
eno izmed krajišč poti b, kot na sliki 6. Če sta obe
krajišči b vmes ali obe zunaj intervala med aZ in aK ,
potem bomo opisali enak kot za obe krajišči b: bo-
disi bomo šli direktno od aZ do aK in s tem že srečali
obe krajišči, ali pa bomo morali enkrat naokrog, da
poberemo obe krajišči. V tem primeru se poti ne se-
kata. Če pa je med aZ in aK le eno krajišče b, se poti
sekata. V tem primeru sta opisana kota različna.
A C
B
C
B
A
C
B
A
C
B
A
C
B
C
A
B
A C
B
C
B
A C
B
C
B
A C
B
C
B
SLIKA 5.
Križišče obǐcajne ceste (sever-jug) in
enosmernega izvoza z avtoceste z
zahoda in nazaj na avtocesto proti
vzhodu.
     
P 50 (2022/2023) 38
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
aZ
aK
bZ
bK
aZ
aK bZ
bK
SLIKA 6.
Prepoznavanje presečišč s pomočjo ciklǐcnega sprehoda. Levo:
sprehoda 9-1-2 in 9-8-2 sta razlǐcno dolga, torej se poti sekata.
Desno: sprehoda 3-1-8 in 3-6-8 sta enako dolga, torej se poti
ne sekata.
Če z mod(x,n) pišemo pozitivni ostanek x po de-
ljenju z n, potem se poti ne sekata, če in samo če
velja enačba
mod(bZ − aZ , n)+mod(aK − bZ , n) =
= mod(bK − aZ , n)+mod(aK − bK , n).
To pa je nekaj, kar računalnik lahko preveri brez
znanja geometrije.
Videli smo, da s pomočjo teorije grafov lahko sis-
tematično opišemo možne semaforne cikle in izbe-
remo tistega, ki najbolje ustreza naši situaciji. To-
vrstno analizo lahko naredimo za poljubno križišče,
na primer za križišče petih cest, pri čemer ugoto-
vimo, da imamo 32 možnih 5-stopenjskih semafor-
nih ciklov, če prepovemo zavijanje na isti izhodni
pas. Tako kompleksna križišča so nepraktična in za
voznike nepregledna, predvsem pa imajo nizko pre-
točnost. V takih primerih raje uporabimo dve za-
poredni križišči, najraje pa kar krožišče. Krožišča
nimajo težav s križanjem poti, še vedno pa imamo
poti, ki se zlivajo v isti vozni pas – vozila se vključu-
jejo na pas, po katerem z leve lahko prihaja vozilo,
ki je že v krožišču.
Bralce vabim, da med čakanjem pri rdeči luči opa-
zujejo, katera različica semafornega cikla velja, kako
se razvrščajo v pasove, in kako se razrešujejo zavoji,
ki jih semafor mogoče ne regulira ločeno. S tem bo
tudi čakanje mogoče postalo nekoliko manj nadle-
žno.
×××
Tri lastnosti
števila 2023
M R
1. Število 2023 je petkrat pohlevno, ker se ga da
izraziti na pet načinov kot vsoto nekaj zaporednih
naravnih števil, denimo x,x+1, . . . , x+n−1. Pri tem
sta števili x in n naravni. Veljati mora torej relacija
x + (x + 1)+ . . .+ (x +n− 1) = 2023.
Vsoto na levi strani znamo poenostaviti, tako da do-
bimo
n(x + (x +n− 1))
2
= 2023
oziroma
n(2x +n− 1) = 2 · 7 · 172.
Desno stran te relacije lahko zapišemo na pet nači-
nov kot produkt dveh faktorjev: 2 · (7 · 172),14 ·
172,34 · (7 · 17),17 · (14 · 17),7 · (2 · 172). Zato
lahko izberemo n = 2,2x+n−1 = 7·172 in dobimo
x = 1011. Podobno sledi za n = 14,2x+n−1 = 172
še x = 138 itd. To pomeni, da veljajo zapisi
2023 = 1011+ 1012 = 138+ 139+ . . .+ 151
= 43+ 44+ . . .+ 76
= 111+ 112+ . . .+ 127
= 286+ 287+ . . .+ 292.
2. Število 2023 je kongruentno, kar pomeni, da ob-
staja pravokoten trikotnik, ki ima za stranice racio-
nalna števila in ploščino 2023.
Ker je 2023 = 7 · 172, je dovolj pokazati, da je 7
kongruentno število. Ni vsako naravno število kon-
gruentno. Najmanjše kongruentno števolo je 5, kar
je vedel že Fibonacci.
Pravokotne trikotnike, ki imajo za stranice a,b, c
(a2 + b2 = c2) naravna števila, to je pitagorejske tri-
kotnike, znamo poiskati s formulami
a =m2 −n2, b = 2mn,c =m2 +n2.