Sirion
Гений-Говорун
 Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
 |
� : Январь 03, 2012, 08:43:00 � |
|
1. Верно ли, что вершинам любого графа можно приписать числовые значения так, чтобы для каждой вершины сумма чисел у её соседей равнялась единице?
2. Верно ли, что вершинам любого графа можно приписать числовые значения так, чтобы для каждой вершины сумма чисел у неё и её соседей равнялась единице?
3. Дан связный граф из n вершин. Какое минимальное количество рёбер понадобится пройти в худшем случае, чтобы обойти все вершины и вернуться в исходную?
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #1 : Январь 03, 2012, 09:35:02 � |
|
|
|
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #2 : Январь 03, 2012, 09:44:45 � |
|
Показать скрытый текст
1. нет (граф с 1 вершиной)
3. труднее всего лазить по деревьям
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #3 : Январь 03, 2012, 09:46:46 � |
|
3 Показать скрытый текст
минимальное количество рёбер = n-1.
каждое нужно пройти по 2 раза.
|
|
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #4 : Январь 03, 2012, 09:47:14 � |
|
всё верно
4. А верно ли, что если в 3. граф - не дерево, то это обязательно нам поможет?
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #5 : Январь 03, 2012, 09:48:23 � |
|
moonlight, твоя мельница во 2 задаче решаема - основание каждой лопасти (точка, откуда она растёт) делаем 1, все остальные 0
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #6 : Январь 03, 2012, 09:51:27 � |
|
гм... проглядел
у меня была какая-то более простая конструкция для 2.
особо не вдумываясь, решил, что эта тоже сойдёт
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #7 : Январь 03, 2012, 09:52:33 � |
|
4. А верно ли, что если в 3. граф - не дерево, то это обязательно нам поможет? да, рисуем цикл и дополняем его оставшимися деревьями |
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
iPhonograph
Гений-Говорун
Offline
Сообщений: 2100
СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315
Дискоед
|
|
� Ответ #8 : Январь 03, 2012, 09:53:18 � |
|
я сомневаюсь, что во 2 задаче ответ "нет"
|
|
|
|
|
Записан
|
"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #9 : Январь 03, 2012, 10:15:42 � |
|
moonlight, твоя мельница во 2 задаче решаема - основание каждой лопасти (точка, откуда она растёт) делаем 1, все остальные 0
ага |
|
|
|
|
Записан
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #10 : Январь 03, 2012, 10:39:48 � |
|
В 2. ответ "нет", я перепроверил свою конструкцию три раза.
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
moonlight
Умник
Offline
Сообщений: 741
СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232
|
|
� Ответ #11 : Январь 03, 2012, 22:40:23 � |
|
|
Зачем откладывать на завтра то, что можно отложить на послезавтра?
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #12 : Январь 03, 2012, 22:42:47 � |
|
да, именно
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
|
