Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.
Здравствуйте, если не трудно, можете пожалуйста помочь решить задания по дискретной математике. А вообще, как представить графовую задачу в виде ЗЛП? если знаешь, подскажи, пожалуйста.
def get_circle(matrix: list[list[int, ]]) -> list[int, ]: # помним что list это изменяемый объект в python! _matrix = deepcopy(matrix) S = [0] C = [] while len(S): for i in range(len(_matrix[S[-1]])): if (_matrix[S[-1]][i] == 1) and (i not in C): _matrix[S[-1]][i] = 0 _matrix[i][S[-1]] = 0 S.append(i) break else: C.append(S.pop()) if len(S): _matrix[C[-1]][S[-1]] = 1 _matrix[S[-1]][C[-1]] = 1 return C
Спасибо, всё просто и понятно!
Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы:
Задачи на множествах:
• разбиение множества на подмножества;
• задача о наименьшем разбиении (ЗНР);
• задача о наименьшем покрытии (ЗНП).
Группа задач на достижимость:
• взаимная достижимость вершин;
• кратчайшие пути между вершинами;
• выделение сильно связанных компонент.
Группа задач на размещение:
• независимые вершины и клики;
• доминирующие множества;
• раскраски;
• центры;
• p-центры;
• p-медианы.
Остовные деревья
Группа задач о потоках:
• максимальный поток в сети;
• поток, ограниченный сверху и снизу;
• минимальная стоимость потока.
Паросочетания на взвешенных графах:
• паросочетание в двудольном графе;
• паросочетание в произвольном графе.
Цикл Эйлера и задача почтальона на взвешенных графах:
• на неориентированном графе;
• на орграфе.
Задачи Гамильтона и коммивояжёра на взвешенных графах:
• разомкнутая задача Гамильтона;
• замкнутая задача Гамильтона (контур);
• комбинирование методов для задач Гамильтона;
• замкнутая и разомкнутая задачи коммивояжёра.
Спасибо,пацаны
Здравствуйте, могли бы вы выложить код на питоне?
Здравствуйте, если не трудно, можете пожалуйста выложить или отправить код на питоне, хочется ознакомиться, курсовую пишу по дискретной математике
Здравствуйте, если не трудно, можете пожалуйста помочь решить задания по дискретной математике. А вообще, как представить графовую задачу в виде ЗЛП? если знаешь, подскажи, пожалуйста.
def get_circle(matrix: list[list[int, ]]) -> list[int, ]:
# помним что list это изменяемый объект в python!
_matrix = deepcopy(matrix)
S = [0]
C = []
while len(S):
for i in range(len(_matrix[S[-1]])):
if (_matrix[S[-1]][i] == 1) and (i not in C):
_matrix[S[-1]][i] = 0
_matrix[i][S[-1]] = 0
S.append(i)
break
else:
C.append(S.pop())
if len(S):
_matrix[C[-1]][S[-1]] = 1
_matrix[S[-1]][C[-1]] = 1
return C
@@СергейГерасимов-э5м спасибо) стал разработчиком в итоге, видимо оказалось проще самому запрогать)