фа не більшу за його діаметру.
Вершина v називається центральною, якщо e (v)=r (G). Безліч всіх центральних вершин графа називається його центром. Граф може мати єдину центральну вершину або декілька центральних вершин. Нарешті, центр графа може збігатися з безліччю всіх вершин. Наприклад, центр простий ланцюга Pn при парному числі вершин n складається рівно з двох вершин, а при непарному - з однієї; для циклу ж Cn всі вершини є центральними.
Задача знаходження центральних вершин графа постійно виникає в практичній діяльності людей. Нехай, наприклад, граф представляє мережу доріг, тобто вершини його відповідають окремим населеним пунктам, а ребра - дорогам між ними. Потрібно оптимально розмістити лікарні, магазини. У подібних ситуаціях критерій оптимальності часто полягає в оптимізації найгіршого випадку, тобто в мінімізації відстані від місця обслуговування до найбільш віддаленого пункту. Отже, місцями розміщення повинні бути центральні вершини графа.
Реальні завдання (їх називають мінімаксними завданнями розміщення) відрізняються від ідеальної тим, що доводиться ще враховувати інші обставини - фактичні відстані між окремими пунктами та вартість, час проїзду та інше. Для того щоб врахувати це, використовують зважені графи.
. Додаток теорії графів у різних галузях науки і техніки
Інформація.
Двійкові дерева відіграють дуже важливу роль у теорії інформації. Припустимо, що певне число повідомлень потрібне закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів і одиниць. Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана.
Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або да raquo ;, або немає raquo ;. Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. Опитування завершується, коли вдається встановити те, що було потрібно.
Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на чергове запитання буде залежати від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Хімія
Ще А. Келі розглянув задачу про можливі структурах насичених (або граничних) вуглеводнів, молекули яких задаються формулою:
n H 2n +2 ??
Всі атоми вуглеводню Четирьохвалентний, всі атоми водню одновалентних. Молекула кожного граничного вуглеводню являє собою дерево. Якщо видалити всі атоми водню, то решта атоми вуглеводню також будуть утворювати дерево, кожна вершина якого має ступінь не вище 4. Отже, число можливих структур граничних вуглеводнів, т. Е. Число гомологів даної речовини, дорівнює числу дерев з вершинами ступені не більше чотирьох.
Таким чином, підрахунок числа гомологів граничних вуглеводнів також приводить до задачі про перерахування дерев певного типу. Це завдання і її узагальнення розглянув Д. Пойа.
Електротехніка.
Ще недавно однією з найбільш складних і утомливих завдань для радіоаматорів було конструювання друкованих схем.
Друкованій схемою називають платівку з якого-небудь діелектрика (ізолюючого матеріалу), на якій у вигляді металевих смужок витравлені доріжки. Перетинатися доріжки можуть тільки в певних точках, куди встановлюються необхідні елементи (діоди, тріоди, резистори та інші), їх перетин в інших місцях викличе замикання електричного кола.
У ході вирішення цього завдання необхідно викреслити плоский граф, з вершинами у зазначених точках.
. Практична частина
a)
Матриця суміжності:
Матриця інцидентності:
Матриця відстаней:
Ексцентриситети вершин:
e (x 1)=2
e (x 2)=2
e (x 3)=2
e (x 4)=2
e (x 5)=1 (x 6)=2
Передавальні числа вершин:
p (x 1)=6 (x 2)=7 (x 3)=6 (x 4)=7 (x 5)=5
p (x 6)=7
Діаметр графа дорівнює 2, радіус - 1. Центр графа знаходиться в вершині X 5. Медіани графа: x 2, x 4, x 6.
