راس یا Vertex (تئوری نمودار)
نمودار با 6 راس و 7 لبه که در راس شماره 6 در سمت چپ سمت راست یک برگه برگ یا یک راس آویز قرار دارد.
در ریاضیات ، و به طور خاص در نظریه گراف ، یک راس (الجمع راس ) و یا گره واحد بنیادی که نمودار شکل می گیرند: یک گراف بدون جهت متشکل از مجموعه ای از رئوس و مجموعه ای از لبه (جفت نامرتب رأس)، در حالی که گراف جهت متشکل از مجموعه ای از رئوس و مجموعه ای از کمان (زوج مرتب از رئوس). در نمودار نمودار ، یک راس معمولاً توسط یک دایره با یک برچسب نمایش داده می شود و یک لبه توسط یک خط یا فلش نمایش داده می شود که از یک راس به دیگری امتداد دارد.
از نظر تئوری نمودار ، رئوسها به عنوان اشیاء بدون ویژگی و غیرقابل تفکیک رفتار می شوند ، اگرچه بسته به کاربردی که از آن نمودار بوجود می آیند ، ممکن است دارای ساختار اضافی باشند. به عنوان مثال ، یک شبکه معنایی گرافی است که در آن رئوسها مفاهیم یا کلاس اشیاء را نشان می دهند.
گفته می شود که دو راس تشکیل دهنده ی لبه ، نقاط انتهایی این لبه است و گفته می شود که این لبه حادثه ای به سمت راسها است. گفته می شود که یک راس w در حالی که یک نمودار حاوی یک لبه ( v ، w ) باشد ، مجاور یک راس دیگر v است . محله از یک راس V یک IS زیرگراف القایی از نمودار، تشکیل شده توسط تمام رئوس مجاور به V .
فهرست
انواع رئوس [ ویرایش ]
شبکه نمونه با 8 راس (که یکی از آنها جدا شده) و 10 لبه است.
درجه یک راس، δ (V) در یک گراف نشان داده می شود تعداد یال به آن است. راس جدا شده یک راس با درجه صفر است. یعنی یک راس که نقطه پایانی از هر لبه نیست (تصویر مثال یک راس جدا شده را نشان می دهد). [1] راس برگ (همچنین راس آویز ) یک راس با یک درجه است. در یک نمودار کارگردانی ، می توانید outdegree (تعداد لبه های خروجی) ، با علامت 𝛿 + (v) ، از indegree (تعداد لبه های ورودی) ، مشخص شده distingu - (v) را تشخیص دهید. یک راس منبع یک راس با صفر نامشخص است ، در حالی که یک راس سینک یک راس با صفر outdegree است. های simplicial راس همسایه ای است که همسایگانش کلیپی تشکیل می دهند : هر دو همسایه در مجاورت هستند. راس جهانی یک راس است که در مجاورت هر راس دیگر در گراف است.
راس برش یک راس است که با حذف آن می توانید نمودار باقیمانده را جدا کنید. جدا راس مجموعه ای از رئوس حذف که نمودار باقی مانده را به قطعات کوچک جدا است. گراف k- راس متصل یک گراف که از بین بردن کمتر از است ک راس همیشه برگ گراف باقی مانده متصل می شود. یک مجموعه مستقل مجموعه ای از رئوس است که هیچ دو از آنها در مجاورت قرار ندارند و یک پوشش راس مجموعه ای از رئوس است که حداقل یک نقطه انتهایی از هر لبه در نمودار را شامل می شود. فضای راس های یک گراف یک فضای برداری داشتن مجموعه ای از بردارهای پایه متناظر با رئوس گراف است.
نمودار دارای vertex-transitive است اگر دارای تقارنهایی باشد که هر راس را به هر راس دیگر نشان می دهد. در زمینه شمارش نمودار و ایزومورفیسم گراف ، تمایز بین راسهای دارای برچسب و راسهای بدون برچسب مهم است . یک راس برچسب راس است که با اطلاعات اضافی در ارتباط است و باعث می شود تا از دیگر راس های دارای برچسب متمایز شوند. دو نمودار را می توان ایزومورفیک در نظر گرفت که مکاتبات بین رئوس آنها با برچسب های مساوی راسها بالا می رود. یک راس بدون برچسب است که می تواند جایگزین هر راس دیگر شود فقط بر اساس مجاورت آن در نمودار و بر اساس هیچ اطلاعات اضافی نیست.
عمودهای موجود در نمودار شبیه به رئوسهای چند ضلعی نیستند : اسکلت یک چندپایه یک گراف را تشکیل می دهد ، که عمودهای آنها راسهای چند ضلعی هستند ، اما عمودهای چند ضلعی دارای ساختار اضافی (محل هندسی آنها) هستند. فرض بر این نیست که در تئوری نمودار حضور داشته باشد. شکل راس یک راس در یک جسم چند وجهی مشابه همسایگی یک رئوس یک گراف است.
منبع