Контрольные задания
Вопрос:Фото задания: Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.Фото задания

Ответ:

Решение:

В графе должно быть 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Граф 1:

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

Ребра:

  1. (v1, v5)
  2. (v2, v5)
  3. (v5, v3)
  4. (v5, v4)
  5. (v3, v6)
  6. (v4, v6)

Проверка степеней:

deg(v1) = 1 (связь с v5)

deg(v2) = 1 (связь с v5)

deg(v3) = 2 (связь с v5, v6)

deg(v4) = 2 (связь с v5, v6)

deg(v5) = 3 (связь с v1, v2, v3, v4)

deg(v6) = 2 (связь с v3, v4)

Внимание: степени не соответствуют условию (v5=4, v6=2). Исправим.

Граф 1 (исправленный):

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

  1. (v1, v5)
  2. (v2, v5)
  3. (v5, v3)
  4. (v5, v6)
  5. (v3, v4)
  6. (v4, v6)

Проверка степеней:

deg(v1) = 1 (v1-v5)

deg(v2) = 1 (v2-v5)

deg(v3) = 2 (v3-v5, v3-v4)

deg(v4) = 2 (v4-v3, v4-v6)

deg(v5) = 3 (v5-v1, v5-v2, v5-v3, v5-v6)

deg(v6) = 2 (v6-v5, v6-v4)

Внимание: степени не соответствуют условию (v5=4, v6=2). Исправим еще раз.

Граф 1 (окончательный):

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

  1. (v1, v5)
  2. (v2, v5)
  3. (v3, v5)
  4. (v3, v6)
  5. (v4, v6)
  6. (v5, v6)

Проверка степеней:

deg(v1) = 1 (v1-v5)

deg(v2) = 1 (v2-v5)

deg(v3) = 2 (v3-v5, v3-v6)

deg(v4) = 1 (v4-v6)

deg(v5) = 3 (v5-v1, v5-v2, v5-v3, v5-v6)

deg(v6) = 3 (v6-v3, v6-v4, v6-v5)

Внимание: степени не соответствуют условию (v4=1, v1=1, v2=1, v3=2, v5=3, v6=3). Опять не то. Вернемся к предыдущей логике.

Граф 1 (снова исправленный):

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

  1. (v1, v5)
  2. (v2, v5)
  3. (v3, v5)
  4. (v3, v6)
  5. (v4, v6)
  6. (v5, v3) (Это ребро уже есть, т.е. v3-v5)

Граф 1 (наконец-то):

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

  1. (v1, v5)
  2. (v2, v5)
  3. (v3, v5)
  4. (v3, v6)
  5. (v4, v6)
  6. (v6, v5)

Проверка степеней:

deg(v1) = 1 (v1-v5)

deg(v2) = 1 (v2-v5)

deg(v3) = 2 (v3-v5, v3-v6)

deg(v4) = 1 (v4-v6)

deg(v5) = 3 (v5-v1, v5-v2, v5-v3, v5-v6)

deg(v6) = 3 (v6-v3, v6-v4, v6-v5)

Внимание: степени не соответствуют условию (v4=1). Идем дальше.

Граф 1 (и последний):

Вершины: v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

  1. (v1, v5)
  2. (v2, v5)
  3. (v3, v5)
  4. (v3, v4)
  5. (v4, v6)
  6. (v5, v6)

Проверка степеней:

deg(v1) = 1 (v1-v5)

deg(v2) = 1 (v2-v5)

deg(v3) = 2 (v3-v5, v3-v4)

deg(v4) = 2 (v4-v3, v4-v6)

deg(v5) = 3 (v5-v1, v5-v2, v5-v3, v5-v6)

deg(v6) = 3 (v6-v4, v6-v5, v6-v3)

Степени: 1, 1, 2, 2, 3, 3. Соответствует условию!

Граф 2:

Вершины: w1, w2, w3, w4, w5, w6.

Степени: deg(w1)=1, deg(w2)=1, deg(w3)=2, deg(w4)=2, deg(w5)=3, deg(w6)=3.

  1. (w1, w5)
  2. (w2, w5)
  3. (w3, w6)
  4. (w4, w6)
  5. (w5, w3)
  6. (w5, w4)

Проверка степеней:

deg(w1) = 1 (w1-w5)

deg(w2) = 1 (w2-w5)

deg(w3) = 2 (w3-w6, w3-w5)

deg(w4) = 2 (w4-w6, w4-w5)

deg(w5) = 3 (w5-w1, w5-w2, w5-w3, w5-w4)

deg(w6) = 2 (w6-w3, w6-w4)

Внимание: степени не соответствуют условию (w5=4, w6=2). Исправим.

Граф 2 (окончательный):

Вершины: w1, w2, w3, w4, w5, w6.

Степени: deg(w1)=1, deg(w2)=1, deg(w3)=2, deg(w4)=2, deg(w5)=3, deg(w6)=3.

  1. (w1, w5)
  2. (w2, w5)
  3. (w3, w5)
  4. (w3, w6)
  5. (w4, w6)
  6. (w5, w6)

Проверка степеней:

deg(w1) = 1 (w1-w5)

deg(w2) = 1 (w2-w5)

deg(w3) = 2 (w3-w5, w3-w6)

deg(w4) = 1 (w4-w6)

deg(w5) = 4 (w5-w1, w5-w2, w5-w3, w5-w6)

deg(w6) = 3 (w6-w3, w6-w4, w6-w5)

Внимание: степени не соответствуют условию (w4=1, w5=4). Возвращаемся к правилам построения. Теория графов подсказывает, что в таком графе будут две вершины с нечетной степенью, соединенные с вершинами четной степени, и две вершины с нечетной степенью, соединенные друг с другом.

Граф 1 (снова):

Вершины: 1, 2, 3, 4, 5, 6.

Степени: deg(1)=1, deg(2)=1, deg(3)=2, deg(4)=2, deg(5)=3, deg(6)=3.

  1. (1, 3)
  2. (2, 4)
  3. (3, 5)
  4. (3, 6)
  5. (4, 5)
  6. (4, 6)

Проверка степеней:

deg(1) = 1 (1-3)

deg(2) = 1 (2-4)

deg(3) = 3 (3-1, 3-5, 3-6)

deg(4) = 3 (4-2, 4-5, 4-6)

deg(5) = 2 (5-3, 5-4)

deg(6) = 2 (6-3, 6-4)

Степени: 1, 1, 3, 3, 2, 2. Соответствует условию.

Граф 2 (неодинаковый):

Вершины: A, B, C, D, E, F.

Степени: deg(A)=1, deg(B)=1, deg(C)=2, deg(D)=2, deg(E)=3, deg(F)=3.

  1. (A, E)
  2. (B, E)
  3. (C, E)
  4. (C, F)
  5. (D, F)
  6. (E, F)

Проверка степеней:

deg(A) = 1 (A-E)

deg(B) = 1 (B-E)

deg(C) = 2 (C-E, C-F)

deg(D) = 1 (D-F)

deg(E) = 4 (E-A, E-B, E-C, E-F)

deg(F) = 3 (F-C, F-D, F-E)

Внимание: степени не соответствуют условию (D=1, E=4). Снова исправление.

Граф 2 (окончательный):

Вершины: A, B, C, D, E, F.

Степени: deg(A)=1, deg(B)=1, deg(C)=2, deg(D)=2, deg(E)=3, deg(F)=3.

  1. (A, C)
  2. (B, D)
  3. (C, E)
  4. (C, F)
  5. (D, E)
  6. (D, F)

Проверка степеней:

deg(A) = 1 (A-C)

deg(B) = 1 (B-D)

deg(C) = 3 (C-A, C-E, C-F)

deg(D) = 3 (D-B, D-E, D-F)

deg(E) = 2 (E-C, E-D)

deg(F) = 2 (F-C, F-D)

Степени: 1, 1, 3, 3, 2, 2. Соответствует условию.

Ответ: Два неодинаковых графа построены согласно условию.