Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Примеры выполнения заданий. Докажите, что валентности вершин графов А и Б совпадают.
|
|
Докажите, что валентности вершин графов А и Б совпадают.
 |
А Б
Решение: А) d(v1)=2, d(v2)=3, d(v3)=3, d(v4)=2, d(v5)=3, d(v6)=3.
Б) d(v1)=2, d(v2)=3, d(v3)=3, d(v4)=2, d(v5)=3, d(v6)=3.
Докажите, что графы G1(X1, E1)и G2(Y2, E2)изоморфны.
   
|
 
   
|
Решение:
  X1(3, 3)
|  X2(4, 4)
|   X3(3, 3)
| X4(2, 2) | X5(2, 2) |
| Y1(4, 4) | Y2(2, 2) | Y3(3, 3) | Y4(3, 3) | Y5(2, 2) |
В результате получим соответствие:
Следовательно, графы G1(X, E) и G2(Y, E)изоморфны.
Решите задачу по вычислению валентности вершин графа
Школьник сказал своему приятелю: - У нас в классе 35 человек. Каждый из них дружит ровно с 11 одноклассниками.
Не может этого быть, - сразу ответил приятель, победитель математической олимпиады. Почему он так решил?
Решение: представим себе, что между каждыми двумя друзьями протянута ниточка. Тогда каждый из 35 учеников будет держать в руке 11 концов ниточек, и значит, всего у протянутых ниточек будет 11∙ 
35 = 385 концов. Но общее число не может быть нечётным, так как у каждой ниточки 2 конца.