Какие графы имеете в виду: регулярные или нерегулярные (в заголовке темы).
Есть теорема ’’Теорема Кёнига’’: В графе все циклы чётные тогда и только тогда, когда граф является двудольным. Т.е. если нет циклов нечётной длины - граф двудольный. Вершины одной доли попарно не смежные.
Регулярный граф характеризуется одинаковой степенью для всех вершин. В двудольном графе - две доли. Матрица смежности, если сначала пронумеровать вершины одной доли, а потом второй будет характерна следующему:
0....01.0.1
...
0....01.010.1
1.01.10..0
...
1.10.10..0
В общем, нули только в первом и четвёртом квадратике, исключаем диагональ, а можно и не исключать.
Доказательство довольно простое, но может, есть и лучше.
Количество рёбер инцидентных некому подмножеству попарно не смежных вершин определяем как р=k*s, где k - количество вершин, s- их степень. Поскольку граф двудольный, то р1=р2, р1,р2 – общее количество рёбер инцидентных первой и второй доле соответственно, тогда k1*s=k2*s -> k1=k2, что и требовалось доказать.
Это сообщение было отредактировано гостем, оставившим это сообщение 13.12.08 15:09.
