![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Пример 15. Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими?Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими? Постройте граф. Решение. Вариантов таких компаний может быть два.
Рис.5
В первом случае а) мы имеем связный граф, во втором б) – несвязный. Ребро (
Рис.6
В исходном графе ребро ( Существует несколько признаков мостов: 1) Ребро ( 2) Ребро 3) Ребро Связный граф без циклов называется деревом.
|