رأس (نظریه گراف)

رأس[1] (به انگلیسی: vertex) یا گره[2] (به انگلیسی: node) در ریاضیات و نظریه گراف، یکی از یکاهای بنیانی گراف است. گراف مجموعه‌ای از گره‌ها و لبه‌هایی که این گره‌ها را وصل کرده‌اند (هابندیده‌اند). گرافی بی‌سو مجموعه‌ای از گره‌ها و مجموعه‌ای از یال‌ها (دوتایی‌هایی از گره‌ها) است. گرافی باسو دربردارندهٔ مجموعه‌ای از گره‌ها و مجموعه‌ای از کمان‌ها (دوتایی‌هایی مرتب از گره‌ها) است. برای نمایش گراف، گره‌ها با دایره‌ها (پَرهون‌ها) و لبه‌ها با خط‌هایی یا کمان‌هایی که از گره‌ای بیرون آمده‌اند و به گره‌ای دیگر درمی‌آیند، نمایانیده می‌شوند.

گرافی بی‌سو با ۶ گره و ۷ یال. گرهٔ شمارهٔ ۶ برگ است.

گره‌ها گاه دارای برچسب یا برچسب‌هایی‌اند. گره‌ای برچسب‌دار شی‌ای با داده‌هایش را می‌نمایاند (داده‌ها با برچسب‌ها نشان داده می‌شوند). دو گرهٔ یک لبه، سرهای لبه نامیده می‌شوند و لبه، اُفتان یا فُتان بر این گره‌ها خوانده می‌شود. اگر v و w دو گره باشند، لبه افتان با (v,w) نمایانیده می‌شود. هم‌چنین دو گرهٔ v و w در گرافی همسایه نامیده می‌شوند اگر گراف دارای لبهٔ (v,w) باشد. همین گونه، در یک گراف، همسایگی یک گره، زیرگرافی دربردارنده‌های همهٔ همسایگان گره است.

گونه‌های گره

درجهٔ یک گره شمار یال‌های افتان بر این گره است. گره‌ای جدا (تنها) گره‌ای است با درجهٔ صفر (گره‌ای که سر هیج یالی نیست). گره‌ای برگ است که درجه‌اش یک باشد. برای گره‌ای در گرافی باسو درون‌درجه و برون‌درجه انگاشته می‌شود. دورن‌درجه شمار یال‌های افتانی است که به گره می‌روند و برون‌درجه شمار یال‌هایی است که از گره بیرون می‌آیند. چشمه گره‌ای است با درون‌درجهٔ صفر و چاه گره‌ای است با برون‌درجهٔ صفر. گره‌ای تک‌تافتی گره‌ای است که همسایگانش یک گروهک را بسازند. در یک گروهک همهٔ جفت گره‌ها همسایه‌اند. در یک گراف، گره‌ای جهانی است که همسایهٔ همهٔ گره‌های دیگر باشد.

گره‌ای برش است که برداشتنش گراف را ناهمبند کند. مجموعه‌ای از گره‌ها که برداشتنشان گراف را به تکه‌های کوچک ناهمبند کند جداگر گفته می‌شود. گرافی k-گره-همبند است اگر کمتر از k گرهٔ آن را برداریم، گراف هم‌چنان همبند می‌ماند. یک مجموعه ناوابسته از گره‌ها دربردارندهٔ گره‌هایی است که هیچ جفتی از این گره‌ها با هم همسایه نیستند. به مجموعه‌ای از گره‌ها که دربردارندهٔ دست کم یک سر از هر لبه در گراف است، پوشا کفته می‌شود.

جستارهای وابسته
  • یال

منابع
  1. «رأس تنها» [ریاضی] هم‌ارزِ «isolated vertex»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر هفتم. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۷۸-۹۶۴-۷۵۳۱-۹۴-۸ (ذیل سرواژهٔ رأس تنها)
  2. «گره» [حمل‌ونقل درون‌شهری-جاده‌ای، رایانه و فنّاوری اطلاعات، فیزیک] هم‌ارزِ «node»؛ منبع: گروه واژه‌گزینی. جواد میرشکاری، ویراستار. دفتر اول. فرهنگ واژه‌های مصوب فرهنگستان. تهران: انتشارات فرهنگستان زبان و ادب فارسی. شابک ۹۶۴-۷۵۳۱-۳۱-۱ (ذیل سرواژهٔ گره1)

مشارکت‌کنندگان ویکی‌پدیا. «Vertex (graph theory)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۳ فوریه ۲۰۰۸.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.