Skoči na glavni sadržaj

Osječki matematički list, Vol. 20 No. 1, 2020.

Stručni rad

Niz stupnjeva grafa

Snježana Majstorović ; Odjel za matematiku, Sveučilište J. J. Strossmayera u Osijeku, Osijek
Dolores Begović ; studentica Odjel za matematiku, Sveučilište J. J. Strossmayera u Osijeku, Osijek

Puni tekst: hrvatski pdf 445 Kb

str. 39-52

preuzimanja: 539

citiraj

Sažetak

U radu proučavamo niz stupnjeva neusmjerenog konačnog jednostavnog grafa. Navodimo dva najpoznatija kriterija koji daju nužne i dovoljne uvjete koje mora zadovoljavati niz nenegativnih cijelih brojeva da bi predstavljao niz stupnjeva nekog grafa, teorem Havela i Hakima te teorem Erdősa i Gallaia. Teorem Havela i Hakima je zasnovan na rezidualnom ostatku najvećeg elementa niza stupnjeva.
Na osnovu teorema Havela i Hakima može se razviti algoritam kojim se utvrđuje predstavlja li niz nenegativnih cijelih brojeva niz stupnjeva nekog grafa. Erdős i Gallai su dali nužan i dovoljan uvjet, koji nije algoritamskog tipa, da bi niz bio grafički.

Ključne riječi

jednostavan graf, niz stupnjeva grafa, grafički niz, Havel-Hakimi teorem, skup stupnjeva

Hrčak ID:

252846

URI

https://hrcak.srce.hr/252846

Datum izdavanja:

15.6.2020.

Podaci na drugim jezicima: engleski

Posjeta: 1.178 *