V - векторное пространство над полем $%Z/2Z$%, элементы которого это функции $%f$%: Е → $%Z/2Z$%, где Е это множество рёбер графа G. Эти функции удовлетворяют следующему условию: если ребра е_1,...,е_n образуют цикл, то f(е_1)+...+f(e_n)=0. Доказать, что dimV=q-p, где q-количество вершин, а p - количество компонент связности

задан 22 Мар 19:21

10|600 символов нужно символов осталось
0

Подсчитаем общее число элементов векторного пространства, то есть число функций на рёбрах графа. Если оно равно 2^N, то N будет размерностью.

В каждой связной компоненте произвольным образом отметим одну из вершин. Число не отмеченных вершин равно q-p. Сопоставим каждой вершине 0 или 1, называя это значение оценкой вершины. Отмеченной точке сопоставляем 0; оценки остальных вершин задаём произвольно. Число способов это сделать равно 2^{q-p}.

По каждой оценке вершин построим функцию f. Если e -- ребро, и его концы имеют одинаковую оценку, то полагаем f(e)=0. Если разную, то f(e)=1. Очевидно, что если e1, ... , en образуют цикл, то f(e1)+...+f(en)=0. Действительно, f(e) по построению равно сумме оценок концевых вершин по модулю 2, а тогда в общей сумме все числа сокращаются: (a+b)+(b+c)+...+(z+a)=0.

Рассмотрим обратную конструкцию. Пусть f дана. Сопоставим каждой вершине её оценку по такому правилу. Пусть u принадлежит связной компоненте с отмеченной вершиной v. В ней существует путь p из v в u, ввиду связности. Пусть он состоит из рёбер e1, ... , em. Рассмотрим сумму f(e1)+...f(em) по модулю 2, и объявим её оценкой вершины u. Она не зависит от выбора пути, соединяющего v и u. Если q -- другой такой путь, то pq^{-1} есть цикл. Для него f(pq^{-1})=0, где f от пути есть сумма значений f от входящих в него рёбер. Это значит, что f(p)=f(q), то есть оценка от выбора пути не зависит. Дополнительно заметим, что из v в u=v ведёт пустой путь, для которого сумма рёбер пуста, то есть принимает значение 0.

Легко видеть, что описанное выше соответствие (в обе стороны) задаёт биекцию между множеством функций из условия и множеством оценок на вершинах. Последних имеется 2^{q-p}, как выше было установлено. Поэтому dim V=q-p.

ссылка

отвечен 22 Мар 21:08

Спасибо, красивое решение

(23 Мар 2:38) Бастиан
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×133

задан
22 Мар 19:21

показан
62 раза

обновлен
23 Мар 2:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru