Roman Osipov 
Долгожитель
|
        
Теория графов.
|
Всего сообщений: 2356 | Присоединился: май 2007 | Отправлено: 19 апр. 2009 14:34 | IP
|
|
lorik08
Новичок
|
Дан набор вершин графа (a1,a2,a3....a20) . Построить граф, удовлетворяющий данным условиям. Построить к полученному графу дополнение. Является ли данный граф самодополнительным?
Вершины смежны тогда и только тогда, когда i + j кратно 3.
граф я построила и матрицу смежности тоже, а как построить дополнение и узнать самодополняющий он или нет не могу понять
|
Всего сообщений: 6 | Присоединился: май 2009 | Отправлено: 22 мая 2009 3:59 | IP
|
|
Ander Skirnir
Новичок
|
Дополнение (или дополняющий граф) Вы получите, если в своей матрице смежности поменяете вообще все 1 на 0, а затем 0 на 1 только для несовпадающих вершин.
Самодополняющим называется граф, который изоморфен своему дополнению, что по определению должно значить существование биекции из мн. вершин первого графа в мн. вершин второго, сохраняющей смежность. В Вашем случае такой биекции нет, потому что максимальная степень выхода основного графа равна 6, а степень выхода единички (например) графа-дополнения равна 13.
Из этого, кстати, делается простой и полезный вывод, что если у двух графов в матрицах смежности разное кол-во единичек, то они не могут быть изоморфны.
(Сообщение отредактировал Ander Skirnir 22 мая 2009 12:14)
|
Всего сообщений: 10 | Присоединился: апрель 2009 | Отправлено: 22 мая 2009 11:16 | IP
|
|
lorik08
Новичок
|
большое спасибо, насчет самодополняющих графов я все поняла.
|
Всего сообщений: 6 | Присоединился: май 2009 | Отправлено: 22 мая 2009 13:52 | IP
|
|
Jo
Новичок
|
Подскажите пожалуйста
Как называется (по русски и пор английски) подход в теории узлов, основанный на вложениях узлов в "книгу" с фиксированным числом страниц?
|
Всего сообщений: 2 | Присоединился: июль 2009 | Отправлено: 7 июля 2009 17:44 | IP
|
|
crank
Новичок
|
Объясните пожалуйста как построить граф приращений для следующей задачи:
>Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок). Построить граф приращений. И далее идёт собственно сам граф.
Первую часть задачи я решил, а вот информации о том, как строить граф приращения я найти не могу
|
Всего сообщений: 1 | Присоединился: август 2009 | Отправлено: 24 авг. 2009 19:51 | IP
|
|
zebra lenya
Новичок
|
В компании 601 человек, у каждого минимум 25 знакомых (из этой компании). И надо доказать, что возможно посадить 4 из них за круглый стол так, чтобы каждый знал своих соседей.
Естественно, что если доказать для 25 знакомых, то для большего числа все выполнится автоматически. Пока что до меня дошло лишь то, что это неориентированный граф с 601 вершиной и надо найти замкнутое кольцо длиной в 4 вершины.
Причем у 600 вершин минимум 25 ребер, и у одной - 26.
Подсказите, пожалуйста, с чего начать?
Если что, я с 1 курса, очень прошу - лучше проще, чем на малопонятном математическом языке.
ЗЫ: я понятливая
(Сообщение отредактировал zebra lenya 30 нояб. 2009 18:34)
(Сообщение отредактировал zebra lenya 30 нояб. 2009 19:37)
|
Всего сообщений: 2 | Присоединился: ноябрь 2009 | Отправлено: 30 нояб. 2009 18:25 | IP
|
|
Alekseyshalam
Новичок
|
доказать что у гомеоморфных графов число вершин степени d, где d>2, одно и то же
|
Всего сообщений: 2 | Присоединился: декабрь 2010 | Отправлено: 6 дек. 2010 22:08 | IP
|
|
Philip
Новичок
|
помогите доказать, что множества Х и У равномощны, построив взаимооднозначное соответсвие между ними X=N u {0, 1/2} ; Y=Z
и даны три вещественных функции:
f(x)=2x-3
g(x)=x^(3)+7x-8
h(x)=2^(x^(2)+16x)
Надо найти заданные композииции функции fgh, hfg, ffg; явлются ли f, g и h инъекциями, сюрьекциями, биекциями на R; и найти обратные функции к f, g, h, если функции со своими областями определения обратных не имеют, то найти обратные функции их сужениям.
Помогите, ибо завтра контрольную сдавать, а нам ни литературы, ни навыков не дали для решения таких задач. Все попытки решить их - увенчались провалом
|
Всего сообщений: 1 | Присоединился: февраль 2011 | Отправлено: 3 фев. 2011 14:18 | IP
|
|
Kitsune
Новичок
|
Помогите пожалуйста:
Доказать, что обыкновенный граф на n вершинах не является двудольным, если он имеет более n^2/4 рёбер.
Пожалуйста помогите
(Сообщение отредактировал Kitsune 27 фев. 2011 5:54)
|
Всего сообщений: 22 | Присоединился: декабрь 2010 | Отправлено: 27 фев. 2011 5:47 | IP
|
|
|
Форум
2.8.4 Теория графов
