Зірка (теорія графів)
У теорії графів зірка Sk (англ. star) — це повний двочастковий граф K1,k: дерево з єдиним внутрішнім вузлом і k листками (але при k ≤ 1 має k+1 листків і не має внутрішніх вузлів). Крім того, деякі автори визначають Sk як дерево порядку k з максимальною відстанню 2; в цьому випадку зірка k > 2 має k − 1 листок. Зірка з 3-ма ребрами називається клешнею. Зірка Sk називається реберно-граціозною[en], коли k парне і не є такою, коли непарне. Вона є реберно-транзитивною сірниковому графу, і має відстань 2 (при k>1), обхват ∞ (не має циклів), хроматичний індекс k і хроматичне число 2 (при k> 0). Крім того, зірка має велику групу автоморфізмів, а саме симетричну групу з k букв. Зірка також може бути описана, як зв'язний граф, в якому не більше однієї вершини, що має степінь більше одиниці. Зв'язок з іншими типами графівКлешні зустрічаються у визначенні графів без клешень, графів, які не мають підграфів з клешнями.[1][2] Крім того, вони є одним з виняткових випадків теореми ізоморфізму графів Вітні: загалом, графи з ізоморфними реберними графами так само є ізоморфними, за винятком клешень і трикутника K3.[3] Зірка є особливим видом дерева. Як і будь-яке дерево, зірки можуть бути закодовані за допомогою коду Прюфера; послідовність Прюфера для зірки K1,k складається з k-1 копії центральної вершини.[4] Декілька інваріантів графів визначені в термінах зірок. Арборичність — це мінімальна кількість лісів, які може утворити граф таким чином, що кожне дерево в кожному лісі є зіркою,[5] хроматичним числом зірки[en] називається мінімальне число кольорів, необхідних для фарбування його вершин таким чином, щоб кожні два класи кольорів разом утворювали підграф, у якому всі з'єднані компоненти є зірками.[6] Графи з шириною гілок 1 є саме такими графами, де кожна з'єднана компонента є зіркою.[7] ![]() Інші застосуванняМножина відстаней між вершинами клешні є прикладом кінцевого метричного простору, який не можна ізометрично вкласти в евклідів простір будь-якої розмірності.[8] Топологія «Зірка», комп'ютерна мережа змодельована на основі графа-зірки, відіграє важливу роль у розподілених обчисленнях. Геометрична реалізація графа-зірки формується шляхом визначення ребер з інтервалами деякої фіксованої довжини, використовується як локальна модель кривих у тропічній геометрії. Тропічна крива визначається як метричний простір, що локально ізоморфний як метричний граф зірчастої форми. Матричне представленняЗа певної нумерації матричне подання графа-зірки може мати форму стріли. Зауважте, як просте перенумерування вершин графа може вплинути на швидкодію алгоритмів. У випадку методу Гауса використання матриці із заповненим верхнім рядком призведе до згубного для швидкодії алгоритму заповнення нульових комірок.
Джерела
|
Portal di Ensiklopedia Dunia