Računalništvo (FMF)/Vaje/1. kolokvij 2006-2007/Rešitev 3. naloge

Iz MaFiRaWiki

Najprej premislimo, da škorpijon ne more vsebovati dveh vozlišč tipa a (ki je povezano z vsemi, razen z enim vozliščem). Če bi vseboval dve taki vozlišči (eno zagotovo vsebuje), potem vozlišče tipa c ne bi obstajalo - vsako oglišče bi namreč bilo povezano vsaj z enim od vozlišč tipa a, c pa je povezan le z vozliščem tipa b. Sklep velja, če imamo v grafu več kot štiri vozlišča.

Premislimo, kakšna je matrika, če imamo tri vozlišča - vozlišče tipa b je povezano z a in c, torej v matriki sosednosti škorpijona bosta v eni vrstici dve enici in ničla, vozlišče c je povezano le z b, torej v drugi vrstici enica in dve ničli, isto pa tudi pri vozlišču a, ki je prav tako povezano le z b.

Primer:

\begin{bmatrix} 0 & 1 & 0  \\ 1 & 0 & 1  \\ 0 & 1 & 0  \\ \end{bmatrix}

Za štiri vozlišča premišljujemo podobno. Vozlišči tipa a in b bosta povezani z natanko dvemi drugimi vozlišči - v dveh vrsticah bosta torej po dve enici in dve ničli, vozlišče tipa c je povezano le z b, zato bo v matriki sosednosti vrstica z enico in tremi ničlami, podobno kot pri c pa je s četrtim vozliščem.

Primer:

\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix}

Sedaj se lahko osredotočimo na grafe, ki imajo več kot štiri vozlišča - recimo n vozlišč, brez škode za splošnost jih lahko označimo z 1 do n. Najprej preverimo, če je v matriki natanko ena vrstica, ki ima n − 2 enic in dve ničli - ta bo pripadala vozlišču tipu a. Če takšna vrstica ne obstaja ali jih je več, graf ni škorpijon.

Časovna zahtevnost te naloge je O(n2), saj moramo pregledati vsa polja matrike, teh pa je n2.

Če najdemo takšno vrstico, pogledamo, kje je ničla, ki ni na diagonali - s tem najdemo kandidata za vozlišče tipa c. Če je ta ničla na k-tem mestu v vrstici, pregledamo k-to vrstico. Če je graf škorpijon, morajo biti v tej vrstici same ničle in ena enica. Položaj enice nam pove kandidata za vozlišče tipa b. Pregledamo še vrstico tega vozlišča - če je graf škorpijon, vsebuje natanko dve enici in same ničle - ena enica nam kaže položaj vozlišča a, druga pa vozlišča c.

Časovna zahtevnost prejšnjih korakov je bodisi O(n) (če smo pregledovali vrstice) ali O(1). Skupna časovna zahtevnost je torej O(n2).

Glej tudi

Osebna orodja