From Wikipedia, the free encyclopedia
رأس[1] (به انگلیسی: vertex) یا گره[2] (به انگلیسی: node) در ریاضیات و نظریه گراف، یکی از یکاهای بنیانی گراف است. گراف مجموعهای از گرهها و لبههایی که این گرهها را وصل کردهاند (هابندیدهاند). گرافی بیسو مجموعهای از گرهها و مجموعهای از یالها (دوتاییهایی از گرهها) است. گرافی باسو دربردارندهٔ مجموعهای از گرهها و مجموعهای از کمانها (دوتاییهایی مرتب از گرهها) است. برای نمایش گراف، گرهها با دایرهها (پَرهونها) و لبهها با خطهایی یا کمانهایی که از گرهای بیرون آمدهاند و به گرهای دیگر درمیآیند، نمایانیده میشوند.
گرهها گاه دارای برچسب یا برچسبهاییاند. گرهای برچسبدار شیای با دادههایش را مینمایاند (دادهها با برچسبها نشان داده میشوند). دو گرهٔ یک لبه، سرهای لبه نامیده میشوند و لبه، اُفتان یا فُتان بر این گرهها خوانده میشود. اگر v و w دو گره باشند، لبه افتان با (v,w) نمایانیده میشود. همچنین دو گرهٔ v و w در گرافی همسایه نامیده میشوند اگر گراف دارای لبهٔ (v,w) باشد. همین گونه، در یک گراف، همسایگی یک گره، زیرگرافی دربردارندههای همهٔ همسایگان گره است.
درجهٔ یک گره شمار یالهای افتان بر این گره است. گرهای جدا (تنها) گرهای است با درجهٔ صفر (گرهای که سر هیج یالی نیست). گرهای برگ است که درجهاش یک باشد. برای گرهای در گرافی باسو دروندرجه و بروندرجه انگاشته میشود. دورندرجه شمار یالهای افتانی است که به گره میروند و بروندرجه شمار یالهایی است که از گره بیرون میآیند. چشمه گرهای است با دروندرجهٔ صفر و چاه گرهای است با بروندرجهٔ صفر. گرهای تکتافتی گرهای است که همسایگانش یک گروهک را بسازند. در یک گروهک همهٔ جفت گرهها همسایهاند. در یک گراف، گرهای جهانی است که همسایهٔ همهٔ گرههای دیگر باشد.
گرهای برش است که برداشتنش گراف را ناهمبند کند. مجموعهای از گرهها که برداشتنشان گراف را به تکههای کوچک ناهمبند کند جداگر گفته میشود. گرافی k-گره-همبند است اگر کمتر از k گرهٔ آن را برداریم، گراف همچنان همبند میماند. یک مجموعه ناوابسته از گرهها دربردارندهٔ گرههایی است که هیچ جفتی از این گرهها با هم همسایه نیستند. به مجموعهای از گرهها که دربردارندهٔ دست کم یک سر از هر لبه در گراف است، پوشا کفته میشود.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.