1. Доказать, что удаление одного ребра из цикла связного неорграфа не делает его несвязным.
  2. Эйлеровым называется неорграф, в котором существует цикл, проходящий через каждое его ребро. Гамильтоновым называется неорграф, в котором существует простой цикл, проходящий через все его вершины. Привести примеры Э, Г, Э и Г.
  3. Ребро графа называется мостом, если его удаление увеличивает число компонент. Показать, что граф, содержащий мост, не может быть эйлеровым.
  4. Вершина графа называется точкой сочленения, если ее удаление увеличивает число компонент. Показать, что в любом нетривиальном графе есть, по меньшей мере, две вершины, не являющимися точками сочленения.
  5. Как может измениться число компонент графа при добавлении к нему одной дуги.
  6. Пусть задано отношение среди вершин орграфа – принадлежать одной компоненте. Показать, что это отношение эквивалентности и построить фактор-граф для заданного орграфа.

задан 28 Мар '12 21:22

закрыт 28 Мар '12 22:23

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

1

@ХэшКод, а зачем закрыли? Не такой уж простой вопрос, это же не табличный интеграл считать... Впрочем, мое мнение субъективно (сама не решила 4 пункт).

(28 Мар '12 22:29) DocentI
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Домашнее задание". Закрывший - ХэшКод 28 Мар '12 22:23

1
  1. В цикле между любыми двумя вершинами есть два пути, поэтому разрывание одного из них не разрывает граф (это схема, додумайте ее).
  2. Если нужен Г. граф - начертите цикл (например, поставив вершины по кругу). Он же будет и Эйлеровым. Вообще Эйлеров граф получается, если соединить вершины "одним росчерком пера", т.е. провести ребра, не проходя ни по какому дважды.
  3. Решение следует из первой задачи.
  4. ? пока не знаю..
  5. Если дуга связывает вершины из одной компоненты, то число компонент не изменится. Если из разных - уменьшится на 1.
  6. Связность, как я понимаю, рассматривается без учета направления? Т.е. для каждой пары вершин должен существовать связывающий их путь (из неориентированных ребер). У эквивалентности 3 свойства

а) рефлексивность (a ~ a), здесь - a лежит в одной компоненте с собой: верно.
б) симметрия (если a ~ b, то и b ~ a). Т.е. если существует путь из a в b, то существует и путь из b в a - верно, это тот же путь, так как направления ребер не учитываются.
в) транзитивность (если a ~ b и b ~ c, то a ~ c). То есть при наличии путей из a в b и из b в c есть путь из a в c. Это тоже верно, надо только объединить два первых пути.

ссылка

отвечен 28 Мар '12 22:11

10|600 символов нужно символов осталось
Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×824

задан
28 Мар '12 21:22

показан
930 раз

обновлен
28 Мар '12 22:29

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru