Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Пример 15. Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими?




Читайте также:
  1. II. Средства, применяемые при лечении заболеваний, вызванных условно-патогенными грибами (например, при кандидамикозе)
  2. III. Примерная структура фронтального занятия.
  3. TG Дополнительные признаки, например, Case Report - описание случая
  4. V. ПРИМЕРЫ ИССЛЕДОВАНИЯ ФУНКЦИЙ
  5. V. Сравнительный анализ НДС расчетных схем и пример расчета.
  6. Активный транспорт ионов. Механизм активного транспорта ионов на примере натрий-калиевого насоса
  7. Алгоритмы разгона и торможения. Сравнительная оценка алгоритмов. Примеры.
  8. Антиконцепции. Определение и виды. Примеры концепции о «будущем».
  9. Аутсорфинг: понятие, примеры.
  10. Аэробное и анаэробно-аэробное энергообеспечение мышечной деятельности, средства и методы повышения их мощности и емкости на примере избранного вида спорта.

Существует ли компания из шести человек, в которой каждый знаком с двумя, и только с двумя другими? Постройте граф.

Решение.

Вариантов таких компаний может быть два.

 


vvv
а) б)

 

 

 


Рис.5

 

В первом случае а) мы имеем связный граф, во втором б) – несвязный.

Ребро ( ) называется мостом, если в графе G(X,T), полученном после удаления ребра ( ), вершины и несвязны.

 


Рис.6

 

В исходном графе ребро ( ) является мостом.

Существует несколько признаков мостов:

1) Ребро ( ) является мостом тогда, и только тогда, когда ( ) является единственным путем, соединяющим вершины .

2) Ребро ) является мостом тогда, и только тогда, когда найдутся две вершины , такие, что любой путь, соединяющий их, содержит вершины .

3) Ребро ) является мостом тогда, и только тогда, когда оно не принадлежит ни одному циклу.

Связный граф без циклов называется деревом.


Дата добавления: 2015-07-26; просмотров: 2; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты