Семинар МЛ ТИ: «Исследование количеств паросочетаний в некоторых классах графов»

14 марта прошел онлайн-семинар МЛ ТИ, на котором выступил Никита Кузьмин с докладом «Исследование количеств паросочетаний в некоторых классах графов». Паросочетанием графа называется множество попарно несмежных его ребер. Индексом Хосойи (или z-индексом) графа называется количество его паросочетаний. Данный индекс был предложен японским химиком Харуо Хосойя, который экспериментально заметил, что температура кипения некоторых органических химических соединений тем выше, чем выше z-индекс их молекулярных графов. Тем самым, интересна задача по выявлению графов из заданных классов с максимальным или минимальным значением z-индекса. На настоящее время накоплено большое количество чисто математических результатов такого типа, пусть даже они и не имеют непосредственных приложений в химии. Тем не менее, в этой области остается множество открытых вопросов. В докладе будут даны ответы на некоторые из них (и на некоторые другие ранее открытые вопросы, ассоциированные с паросочетаниями в графах). Это доклад автора по его подготовленной кандидатской диссертации.