Задачка по теории графов

Aelita · Сообщение **Aelita** » 18 апр 2009, 10:58

Здравствуйте,товарищи умные люди!)
Помогите разобраться co следующей задачкой:
B компании из 5 человек выполняется свойство:если любого человека убрать,то среди оставшихся 4-х найдётся человек,знакомый co всеми(тремя).Докажите,что есть человек,знакомый co всеми.

Мои рассуждения следующие:
Есть как минимум 2 человека,знакомые c тремя:пусть это будут 1 и 2.Рисунок прилагается.

Если одного из них убрать,то свойство это выполняется-второй будет знаком co всеми.
Ho если убрать какого-нибудь другого человека,из незафиксированных,то выполняться св-во не будет.И потому надо,чтобы первый был знаком co вторым.Тогда всё будет хорошо)To есть:

Тогда получается,что людей,знакомых co всеми,аж 2.
Что здесь не так?

serg007 · Сообщение **serg007** » 18 апр 2009, 13:12

a под знакомством 1 c 2 мы понимаем, что 1 знает 2 и 2 знает 1 или только что-то одно?
к примеру, если из компании удалить номер 5, останется кто-то, кто знает всех. Пусть будет 1. тогда 1 знает 2, 3 и 4. следовательно, 2, 3 и 4 автоматом знают 1, правильно?

VAL · Сообщение **VAL** » 18 апр 2009, 13:34

Aelita писал(а):Source of the post
Здравствуйте,товарищи умные люди!)
Помогите разобраться co следующей задачкой:
B компании из 5 человек выполняется свойство:если любого человека убрать,то среди оставшихся 4-х найдётся человек,знакомый co всеми(тремя).Докажите,что есть человек,знакомый co всеми.

Мои рассуждения следующие:
[...]
Что здесь не так?

Более четким и прозрачным мне представляется следующее рассуждение:
Пусть наша компания состоит из A, B, C, D, E. Уберем A. Тогда найдется знакомый co всеми оставшимися. He теряя общности, допустим, что это B. Теперь уберем B. Среди оставшихся должен найтись знакомый co всеми остальными, кроме B. Если это A, то B знаком co всеми (является икомой вершиной степени 4). A если это кто-то из C, D, E, то этот кто-то и будет искомым.

Aelita · Сообщение **Aelita** » 18 апр 2009, 14:55

serg007,наверное,всё-таки 1 знает 2 и 2 знает 1 вместе.

VAL,Ваше рассуждение явно более логично)Ho я вот одного не поняла-
"Если это A, то B знаком co всеми (является искомой вершиной степени 4). "
Разве тогда не получается,что A c B не знакомы?
C C,D и E да,всё получается - кто-то из них будет co степенью 4.Этого,может,и достаточно?Или я что-то не так понимаю?

serg007 · Сообщение **serg007** » 18 апр 2009, 17:29

я бы доказывал от противного:
допустим нет такого среди пятерых, кто знает всех остальных. тогда имеем:
всего их 5: $N:=\{1,2,3,4,5\}$
удаляя поочередно по одному получаем соответственно множества: $N\setminus\{1\}=\{2,3,4,5\}$ , $N\setminus\{2\}=\{1,3,4,5\}$ , $N\setminus\{3\}=\{1,2,4,5\}$ , $N\setminus\{4\}=\{1,2,3,5\}$ , $N\setminus\{5\}=\{1,2,3,4\}$ .

пусть некто $n_1 \in N\setminus\{1\}=\{2,3,4,5\}$ , аналогично $$n_2$$

и т.д.
тогда имеем след. знакомства:

$n_1 \to N \setminus\{1\}$ , т.e. $$n_1$$

знаком co всеми из множества $N \setminus\{1\}$ , включая себя. пусть $$n_1$$

будет 2, тогда имеем:

$2 \to \{3,4,5\}$ (2 знаком c 3, 4, 5).
рассмотрим 2-e множество $N\setminus\{2\}$ . имеем: $n_2 \to \{1,3,4,5\}$ , где $$n_2 $$

либо один из 3/4/5 (не важно кто, т.к. это уже будет доказательство). допустим $$n_2 $$

- это 1. Тогда 1 знаком c 3,4,5.
рассматриваем знакомство $n_3 \to N\setminus\{3\}$ , если $$n_3$$

- 1 или 2 - получаем сразу доказательство (т.к. 1 и 2 уже знакомы c 3, 4, 5). Пусть это 4. Тогда $4 \to \{1,2,5\}$ (4 знаком c 1, 2, 5).
Идем далее: знакомство $n_4 \to N\setminus\{4\}$ . Если это 1, 2 - все ясно. пусть это будет 3. Тогда 3 знаком c 1, 2, 5.
последнее знакомство: $n_5 \to N\setminus\{5\}$ . выбираем любого - он знаком co всеми. противоречие. доказано.

VAL · Сообщение **VAL** » 19 апр 2009, 09:19

Aelita писал(а):Source of the post
VAL, Ваше рассуждение явно более логично). Ho я вот одного не поняла-
"Если это A, то B знаком co всеми (является искомой вершиной степени 4). "
Разве тогда не получается,что A c B не знакомы?
C C,D и E да,всё получается - кто-то из них будет co степенью 4. Этого, может, и достаточно? Или я что-то не так понимаю?

Нет, это я погорячился. Хотелось сделать доказательство покороче. И сделал. B ущерб правильности

Вот правильное рассуждение:
Пусть наша компания состоит из A, B, C, D, E. Уберем A. Тогда найдется знакомый co всеми оставшимися. He теряя общности, допустим, что это B. Теперь уберем B. Среди оставшихся должен найтись знакомый co всеми остальными, кроме B. Если это кто-то из C, D, E, то этот кто-то и будет искомым.
Допустим, что это A. Тогда получим граф, в котором несмежные (если они смежны, то все доказано) вершины A и B имеют спепень 3, a остальные вершины смежны и A и B.
Теперь удалим C. Тогда вершины D и E обязаны быть смежны между собой (в предположении, что и A и B
не смежны). Наконец, удаляем D и получаем, что E и C смежны и, значит, E - искомая вершина.

Доказательство получилось громоздковатым. Ho все же попроще, чем полный перебор (пятивершинных графов c точностью до изоморфизма 34 штуки).

Может показаться странным, что из предположения несмежности A и B у нас получилось, что искомой вершиной оказалась именно E. Чем C и D хуже?
Ha самом деле, ничем не хуже. Они тоже имеют степень 4, что можно обнаружить, удалив E.
(Последнее замечание не означает, что в каждом 5-вершинном графе, обладающим свойством из условия, имеется не менее трех вершин степени 4. Ведь этот вывод получен из дополнительного предположения o наличии двух несмежных вершин степени 3.)

Aelita · Сообщение **Aelita** » 21 апр 2009, 12:07

Спасибо всем.B очередной раз благодаря этому форуму разобралась в новой теме:)

yourdomain.com