1. Главная
  2. Библиотека
  3. Высшая математика
  4. Укажите бихроматичные графы: (1) Граф имеет ребра и явл...
Решение задачи на тему

Укажите бихроматичные графы: (1) Граф имеет ребра и является двудольным. (2) Граф полный, число его вершин больше двух. (3) Граф обыкновенный, связный, у него есть ребра и их число на единицу меньше числа вершин.

  • Высшая математика
  • #Дискретная математика
  • #Теория графов
Укажите бихроматичные графы:
(1) Граф имеет ребра и является двудольным.
(2) Граф полный, число его вершин больше двух.
(3) Граф обыкновенный, связный, у него есть ребра и их число на единицу меньше числа вершин.

Условие:

Укажите бихроматичные графы:
(1) Граф имеет ребра и является двудольным.
(2) Граф полный, число его вершин больше двух.
(3) Граф обыкновенный, связный, у него есть ребра и их число на единицу меньше числа вершин.

Ответ дайте в формате последовательности 0 и 1 (например, 001): на первом месте запишите 1, если граф (1) бихроматичен, в противном случае запишите 0 ; на втором месте запишите 1, если граф (2) бихроматичен, в противном случае запишите 0; и т.д.

Решение:

Рассмотрим по порядку каждое условие.

  1. Граф задан как двудольный («имеет ребра и является двудольным»). По определению двудольный граф можно раскрасить в два цвета, то есть он и является бихроматичным. Следовательно, граф (1) – бихроматичный.

  2. Граф задан как полный с числом вершин,...

Выбери предмет