Семинар №10

Докладчик: Оганисян Н. А.

Тема доклада:  Resolution of multiple edges.

Дата: 11.03.2024

Время: 14:15

Место: ул. Союзная 144, 7 корпус ЯрГУ им. П.Г. Демидова, аудитория 422.

Аннотация: Пусть нам дан двудольный граф G=(V1, V2, E) с кратными ребрама |V1|=k и |V2|=n, также степень каждой вершины из V1 и V2 равна n и k соответственно. Задача, меняя рёбра по принципу, ab, cd->ad, cb сделать граф без кратных ребер, причём новые рёбра больше нельзя обменивать.
В докладе будет рассказано решение в случаях, когда остаток от деления n на k равен+-2, +-1, 0. Также будет доказано, что можно свести задачу к рассмотрению только тех случаев, когда каждые две вершины из одной доли имеют общую смежную вершину.

Ссылка на запись семинара: https://youtu.be/e-Gr8aHow_o