Примеры Дискретная математика. Граф

 В графе, представленном следующей матрицей смежности, найти все максимальные независимые множества

Решение:

Построим последовательность , где $$S^{10}$$ представляет совокупность независимых множеств: $$S^1=\left\{1\right\}$$ $$S^2=\left\{\right\{\mathrm{1,2}\left\}\right\}$$ $$S^3=\left\{\right\{\mathrm{1,2,3}\left\}\right\}$$ $$S^4=\left\{\right\{\mathrm{1,2,3}\},\{\mathrm{1,4}\},\{\mathrm{3,4}\left\}\right\}$$ $$S^5=\left\{\right\{\mathrm{1,2,3}\},\{\mathrm{1,4}\},\{\mathrm{3,4}\},\{\mathrm{3,5}\left\}\right\}$$ $$S^6=\left\{\right\{\mathrm{1,2,3}\},\{\mathrm{1,4}\},\{\mathrm{3,4}\},\{\mathrm{3,5}\},\{\mathrm{2,6}\},\{\mathrm{4,6}\},\{\mathrm{5,6}\left\}\right\}$$ $$S^7=\left\{\right\{\mathrm{1,2,3}\},\{\mathrm{1,4,7}\},\{\mathrm{3,4}\},\{\mathrm{3,5}\},\{\mathrm{2,6}\},\{\mathrm{4,6,7}\},\{\mathrm{5,6}\left\}\right\}$$ $$S^8=\left\{\right\{\mathrm{1,2,3}\},\{\mathrm{1,4,7}\},\{\mathrm{3,4,8}\},\{\mathrm{3,5,8}\},\{\mathrm{2,6}\},\{\mathrm{4,6,7}\},\{\mathrm{5,6}\},\{\mathrm{2,8}\},\{\mathrm{7,8}\left\}\right\}$$ $$S^9=\left\{\right\{\mathrm{1,2,3,9}\},\{\mathrm{1,4,7}\},\{\mathrm{3,4,8}\},\{\mathrm{3,5,8}\},\{\mathrm{2,6}\},\{\mathrm{4,6,7}\},\{\mathrm{5,6}\},\{\mathrm{2,8}\},\{\mathrm{7,8,9}\left\}\right\}$$ $$S^{10}=\left\{\right\{\mathrm{1,2,3,9}\},\{\mathrm{1,4,7}\},\{\mathrm{3,4,8}\},\{\mathrm{3,5,8,10}\},\{\mathrm{2,6}\},\{\mathrm{4,6,7}\},\{\mathrm{5,6}\},\{\mathrm{2,8,10}\},\{\mathrm{7,8,9}\left\}\right\}$$ Таким образом, максимальными независимыми множествами являются $$\left\{\mathrm{1,2,3,9}\right\},\left\{\mathrm{3,5,8,10}\right\}$$

Если все же Вы не смогли разобраться самостоятельно с какими-либо задачами по Дискретной математике, то Вы можете заказать у нас решение задач по Дискретной математике

новости

поиск по сайту

  2011-2016 г.г. zadanie.by , все права защищены.  

    - --   -  

ИП Пантелей О.А. Св. № 190852728 Мингорисполкома

Ji- -vo