logo
Гусева Дискретная математика для информатиков и економистов 2010

6.10.1. Преобразование прилагательных в числительные

К сожалению, не существует универсальной методики, позволяющей точно определить, может ли быть построен граф с заданными характеристиками. Зато существует набор критериев и признаков, по которым можно определить невозможность построения того или иного графа.

Первое, что необходимо сделать, внимательно прочитав условие задачи, это превратить все прилагательные, описывающие свойства графа, в числительные, попутно формируя представление о свойствах задаваемого графа.

В табл. 6.6 приведены такие соответствия, чаще всего встречающиеся в формулировке задач.

 

 

Таблица 6.6

Соответствие между описанием графа и свойствами

 

 

 

Прилагатель-

Числительное

Что это значит

ное

 

 

Связный

k = 1

В графе ровно одна компонента связ-

 

 

ности

Несвязный

k ≥ 2

В графе более одной компоненты, его

 

 

диаметр точно равен бесконечности

Регулярный

St(vi) = const

Степени всех вершин равны

Регулярный

St(vi) = y

Степени всех вершин равны y. Если

степени y

 

известно n (число вершин), то можно