• ↓
  • ↑
  • ⇑
 
Записи с темой: теория графов (список заголовков)
21:36 

Волновой алгоритм 2

Уже писал про него, один из методов поиска, он же поиск в ширину. Неэффективную реализацию написал (на поиск каждого возможного шага прочесывает всю матрицу), но с некоторыми ошибками. Исправлять потом буду, пока времени не хватает на это. Программа выводит все кратчайшие пути. Все. Но тут сам собой вопрос напрашивается -- а все это сколько? И само собой появилось желание, чтобы программа количество кратчайших путей считала. И сколько я не пытался так ничего и не получилось. Решил пойти от простого, вывести формулу математически для какого-нибудь простого случая, а конкретно для матрицы без препятствий, начало в левом верхнем углу, конец -- в правом нижнем углу. Но и тут был нежданный провал. Вручную посчитал для 3x3 и 4x4 соответственно 5 и 20 путей. Формулу не вывел и, более того, даже не понял как подходить к ней. Кто-нибудь сталкивался с этой задачей? В интернете увы ничего найти не удалось. Любые ссылки, в том числе и на английскую литературу пойдут мне на пользу. Хотелось бы пока в оффлайне думать над решением.

@темы: Теория графов

13:30 

Доказательство нескольких утверждений по графам

Никак не получается, понять как грамотно доказать некоторые утверждения, например:

1) Доказать, что если в графе (без петель и кратных ребер) более 4 вершин, то либо в самом графе, либо в его дополнении содержится цикл.
попытки доказать

2) Если v - разделяющая вершина графа, то она не является разделяющей в его дополнении.

домыслы

3) Показать, что самодополнительный граф связен

@темы: Дискретная математика, Теория графов

14:11 

Задания по теории графов

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.
мои мысли
2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.
очевидное рассуждение

@темы: Дискретная математика, Теория графов

21:30 

Построить производящую функцию

Вообщем жизнь столкнула меня с такой задачкой из теории графов. Нужно построить производящую функцию `U(x)=\sum_{k=0}^{\infty}\frac{u_{k}x^{k}}{k!}` суммы `u_k` симметрийных коэффициентов всех 1-неприводимых диаграмм с вершинами, в которых сходится не более `n` линий и `k` петлями. Вычислить `u_j` для `j <= 5`. Может ли кто-то подсказать как решать? Под 1-неприводимыми диаграммами я понимаю диаграммы которые нельзя разделить на части перерезав лишь одну линию.

@темы: Теория графов

13:34 

Гамильтонов цикл в гиперкубе

DarthSidious
Тигр, Тигр, жгучий страх, Ты горишь в ночных лесах. Чей бессмертный взор, любя, Создал страшного тебя?
Доброго времени суток. У меня возник вопрос касаемо задачи "Гамильтонов цикл в гиперкубе".
Ясно, что в любом гиперкубе, есть хотя бы один гамильтонов цикл.
А можно ли, что либо сказать про подмножество вершин(или ребер) гиперкуба, точнее гамильтонова цикла в этом подмножестве ?

@темы: Теория графов

21:02 

Задача по теории графов

Республиканская олимпиада 10 класса 2007 года в РБ.
читать дальше

@темы: Теория графов, Дискретная математика

21:01 

Задача по теории графов

Городская олимпиада 11 класса 1999 года в РБ.
читать дальше

@темы: Теория графов, Дискретная математика

17:04 

Центры графа

Существует ли граф с не менее, чем пятью центрами, причем расстояние между каждыми двумя центрами равно трем?
Я подумал, а существует ли хотя бы граф, у которого только два центра и они находятся на расстоянии 2 друг от друга? Так вот, я доказал, что такого не может быть, а отсюда следует, что не может быть и графа с двумя центрами и расстоянием между ними 3. Но, больно просто получается, задача не кажется такой уж простой, я ошибаюсь?

@темы: Теория графов

06:25 

Алгоритм Дейкстры

Здравствуйте! С помощью алгоритма Дейкстры ищу кратчайшие пути. В третьей итерации получается, что три временные вершины имеют значение 5. Возможно ли такое? Как поступать дальше?

@темы: Дискретная математика, Математическая логика, Теория графов

20:22 

Еще немного дискретной математики

blackhawkjkee
Возникли проблемы с парой вещей:

1) Как показать транзитивное замыкание на этом графе?


2) Даются числа в следующем порядке: 7 5 6 4 3 8 1
Необходимо построить двоичное дерево поиска исходя из заданных цифр.

@темы: Дискретная математика, Бинарные отношения, Теория графов

23:29 

mkutubi

Емеличев В.А., Мельников О.И. Лекции по теории графов - Наука, 1990, 288 c.
В книге излагаются основы теории графов, обсуждаются некоторые известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов. Каждая глава сопровождается упражнениями. Для студентов специальностей "Математика", "Прикладная математика".
(rar/djvu) yadi.sk


@темы: Литература, Теория графов

12:19 

помогите решить

соответствия между множествами C = {1,2,3,4,5} и D={5,6,7} таково что его график состоит из пар в которых первая компонента взята из множества С а вторая из D и больше первой компаненты. Постройте граф этого соответствия , график этого соответствия в прямоугольной системе координат. Постройте граф противоположного соответствия , график противоположного соответствия в прямоугольной системе координат.

@темы: Дискретная математика, Теория графов

21:41 

Trotil
На stepic.org открылся курс "дискретные структуры", посвящённый комбинаторике и теории графам. На курс можно записаться прямо сейчас. Первый модуль будет доступен еще неделю.

Курс интересен практической направленностью, постоянно возникают задачи со сложными структурами, свойства которых приходится анализировать самостоятельно. Рекомендую его всем, кто хочет о комбинаторике узнать чуть больше, чем это даётся в стандартном курсе теории вероятностей. Я два модуля прошёл.

Пример среднего по сложности задания:

читать дальше

@темы: Дискретная математика, Комбинаторика, Образование, Теория графов

22:37 

Плоское дерево. Теория графов.

Верно ли, что, если "G-плоское дерево, рёбра которого ломаные", то последовательно удаляя все "висячие " рёбра мы в итоге изничтожим дерево?

@темы: Теория графов

23:28 

Здравствуйте! Помогите, пожалуйста, решить задачу по дискретной математике.
Задача.
Определить планарен граф или нет. Если планарен, то построить ему плоский изоморфный, если не планарен, то доказать его непланарность по теореме Портнягина-Куратовского.

@темы: Дискретная математика, Теория графов

00:06 

Дилетант
На плечах гигантов, на спинах электронов
Завтра (уже сегодня) в Яндексе состоится семинар «Workshop on Extremal Graph Theory».
Здесь его программа:
tech.yandex.ru/events/workshops/msk-jun-2014/
И по этой же ссылке обещают онлайн-трансляцию для всех желающих.
Если кому-нибудь интересно, подключайтесь! :)

@темы: Наука, Новости, Теория графов

11:44 

Графы

yoggik_wow
And I'm feeling good.
Добрый день.
Есть вот такая задачка:
Верно ли, что в вершинно k-связном графе любые k+1 вершин лежат на общей цепи?

Я нашла такую теорему, которая утверждает, что если граф k-связен, то любые k вершин принадлежат простому циклу.
Далее я отталкивалась уже от определений. Раз у нас есть k вершин в простом цикле, то это значит, что они различны. А т.к граф k-связен, то у него k+1 вершина, и эта еще одна вершина тоже будет различной (правда не до конца понятно почему). Отсюда следует, что все вершины и ребра различны, а значит это определение общей цепи.

Хотелось бы узнать, правильны ли мои рассуждения?

@темы: Теория графов, Дискретная математика

02:48 

Собственные числа графа(1)

Med-ved
Пушист. Чешите.
Здравствуйте. Это снова я. Я уже обращался к сюда с этим вопросом ранее, но, к сожалению, у меня ничего не получается.
Исследовать собственные числа полного двудольного графа K(n,m).
Я никак не могу доказать, что они равны 0, sqrt(nm) и -sqrt(nm)
Что уж говорить об исследовании кратности.
Я пытался воспользоваться формулой характеристического уравнения через миноры, но, мало того, что у меня не выводится общее доказательство, так я еще и застрял на графе K(3,2)
Прошу помочь.

@темы: Теория графов

18:53 

Собственные числа графа

Med-ved
Пушист. Чешите.
И снова здравствуйте.
У меня такая проблема.
Я пытаюсь рассмотреть собственные числа полного двудольного графа.
Матрица симметрична.
Для графа K(n,n) все чисто и хорошо.
А вот для произвольной биклики как-то не выходит.
Что бы вы посоветовали сделать? Есть ли способы найти определитель такой матрицы смежности?

@темы: Теория графов

08:56 

Регулярные графы

Med-ved
Пушист. Чешите.
Всем доброго времени суток! Пожалуйста, посоветуйте книги по алгебраической теории графов! Мне нужно что-нибудь про регулярные и сильно регулярные графы.

@темы: Теория графов, Посоветуйте литературу!

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная