Skip to the main content

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

Professional paper

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

Full text: croatian pdf 445 Kb

page 39-52

downloads: 749

cite

Abstract

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.

Keywords

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

Hrčak ID:

252846

URI

https://hrcak.srce.hr/252846

Publication date:

15.6.2020.

Article data in other languages: english

Visits: 1.814 *