Поиск алгоритма решения задачи построения графа с заданными условиями

Собственно ищу какой-то стандартный алгоритм.
С дискретной математикой не связан и потому надеюсь, что тут кто-то подскажет, т к мое решение точно не катит.

Построение графа с заданным количеством вершин и заданным минимальным количеством рёбер, инцидентных каждой вершине.

 

only
Если задано для каждой вершины только минимальное количество рёбер, то что мешает сделать у каждой вершины по N-1 ребру?

 

maxdiver
Шутить изволите?

Ладно я уточню

Нужно найти граф покрывающий все вершины
каждая из вершин должна иметь определенное число инцидентных ребер >2 && <n-1

 

Что значит 'инцидентный'?

 

KeSqueer

инцидентные ребра, в смысле - ребра связанные с вершиной.
тут вот описано, более понятно - ->link<-

 

Из каждой вершины исходит одинаковое количество ребер? При чем здесь минимальное? Уточните еще, пожалуйста.

 

пусть мы имеем n вершин и нам нужно k вершин для каждого ребра
1. выбираем две вершины, которые имеют наименьшее число ребер меньше k
2. если таких вершин нет, то выход
3. если такая вершина одна, то соединяем ее с произвольной вершиной
4. если таких вершин две, то соединяем их
5. перейти на 1

Не скажу, что это самый быстродействующий алгоритм, но работать должен

 

Задачу можно переформулировать следующим образом: дана симметричная матрица n x n, состоящая из 0 и 1
Найти такую матрицу, чтобы каждый ее столбец содержал ровно k единиц.

 

scf
Вполне неплохое решение. Следует только добавить проверку условия - не соединены ли уже эти две найденных вершины.
Можно все вершины засунуть в список, первую соединить с последней. Потом по кругу прогонять к-2 раз:
1 Взять следующую вершину
2 найти первую вершину из следующих за ней в списке по циклу с ней еще не соединенную и соединить их

 

KeSqueer

вобщем не всегда возможно соединить все вершины так чтобы количество ребер инцидентных каждой было одинаковым и было равно какому то определенному значению

scf

вобще я имел ввиду что на входе n вершин и k- минимальное количество ребер связанных с каждой вершиной

изначально ребер связывающих какие-либо вершины нет, т е по алгоритму сразу выход
и дале пусть даже изначально вершины связаны в кольцо выходит по алгоритму к соседним(уже связанным вершинам) будет добавлятся еще одно ребро, а так увы нельзя

Видать обьяснение туманное слишком

 

вот например

n = 10
k = 2



n = 10
k = 3


n = 10
k = 4

 

Чем #9 не подходит? Старался сделать именно так.

 

для нечетного количества вершин

n = 7
k = 2


n = 7
k = 3

вот тут видно что 7 вершина имеет 4 инцидентных ребра
но минимум по всему графу - 3 ребра

n = 7
k = 4

 

сори пропустил комент
сейчас покажу почему не подходит

 

KeSqueer

Хотя нет
перепроверил и все верно
твой способ на каждом проходе кроме последнего дает
четное количество ребер инцидентных вершине
2-4-6 и тд до n-1 включительно
спасибо за помощь

 

А вот на таком тесте как будет работать: n=6, k=3?
Если я правильно понял ваш алгоритм, то он соединит:
1-2, 2-3, 3-4, 4-5, 5-6, 6-1, затем 1-3, 2-4, затем у него останутся вершины 5 и 6 с недостающим 1 ребром, но их соединить он не сможет, и ему придётся сделать 2 ребра (например, 5-1 и 6-2, неважно), т.е. на 1 ребро больше оптимума.

Оптимум: 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, и затем 1-3, 4-6, 2-5.

Если я нигде не ошибся, получается, алгоритм неоптимальный у вас...

 

maxdiver
в том способе имелось в виду следующее

1 проход - кольцо

а второй

1-3
2-4
3-5
4-6
5-1
6-2

на каждом проходе добавляется по 2 инцидентных ребра, что я в принципе и написал

 

-del-

 

only, зачем добавлять всегда по 2, если k нечётно? Он же вообще по 4 ребра добавит вместо 3.

Вот последний проход и интересует

 

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

Нечетное количество инцидентных каждой вершине ребер, как мне кажется, найти не всегда возможно, если например вершин нечетное количество.
А вот с четным проблем нет.
И алгоритм очень простой.

Если видишь другое решение - подскажи.