گراف

از shaazzz
(تغییرمسیر از گراف ساده)
پرش به ناوبری پرش به جستجو

گراف شامل یک مجموعه V ( راس ها ) و یک چند مجموعه E ( یال ها ) است که . در المپیاد کامپیوتر معمولا گراف های متناهی مورد بحث هستند که در آن ها مجموعه راس ها و یال ها متناهی اند.

گراف بی جهت[ویرایش]

اگر جهت یال برای ما مهم نباشد یعنی یال (u,v) را با یال (v,u) هم ارز در نظر بگیریم، گراف حاصل یک گراف بی جهت است.

گراف ساده[ویرایش]

به یک گراف بی جهت، گراف ساده می گوییم اگر و تنها اگر بین هر دو راس حداکثر یک یال باشد و بین یک راس و خودش یال نباشد.