ВУЗ:
Составители:
68
(r
2
– r)(s
2
–s), m = 2r; n = 2s;
(r
2
– r)s
2
, m = 2r; n = 2s + 1;
I(m,n)
≥
r
2
(s
2
–s), m = 2r + 1; n = 2s;
r
2
s
2
, m = 2r + 1; n = 2s + 1.
Например, пусть m=3 и n=3 (детская задача). Тогда 3=2r+1 и
3=2s+1; 3–1=2r; r=1 и s=1, следовательно, I(3,3)=1, т.е. обязательно
минимум одно пересечение.
Числовые характеристики графов. Решение многих техниче-
ских задач методами теории графов сводится к определению тех или
иных характеристик графов. Числовые характеристики графов - это
функции, заданные на множестве
возможных графов и принимающие
значение из некоторого множества чисел. Предельно простыми ха-
рактеристиками являются число вершин n=/X/ и число дуг m=/U/
(ребер) графа G=<X,U>.
Цикломатическое число
υ(G). Для определения этой характери-
стики необходимо ввести понятие компоненты связности графа. Ес-
ли две вершины графа соединены хотя бы одной цепью, то говорят,
что эти вершины принадлежат одной компоненте графа. Следова-
тельно, граф распадается на компоненты так, что вершины, принад-
лежащие одной компоненте, связаны и в то
же время ни
одна вершина не соединена
цепью с какой-либо вершиной принадле-
жащей другой компоненте. Несвязный
граф имеет минимум две компоненты. На
рис. 2.36 G имеет две компоненты. Ясно,
что если G имеет одну компоненту, то он
является связным. Цикломатическим числом
υ(G) графа G называет-
ся наименьшее число ребер, удаление которых приводит к графу без
циклов.
1 2
3 5
4
Рис. 2.36
Страницы
- « первая
- ‹ предыдущая
- …
- 70
- 71
- 72
- 73
- 74
- …
- следующая ›
- последняя »
