Дискретная математика

142 V2 Хз Рис. 5.19 ^2 •*3 ^5 ^"1 - 1 0 0 0- А= Vj -1 1 -1 1 0 0 0 1 0 -1 V4 U 0 0 -1 1 Для орграфа можно доказать, что ранг А тоже равен п-р. Кроме матриц смежности, достижимости и инциденций вводят ряд других матриц, характеризующих графы: матрица весов, циклов, матрица разрезов и другие. Каждая из них удобна для изучения некоторых свойств графа. Когда рисуешь дерево, нужно чувствовать, к оно растёт. СуШи Лес безмолвен. На просеках пусто. Нынче хачод у ветра в чести. Нет, не может он теплые чувства. Словно зелень листвы, унести. М. Джалиль § 10. Деревья Связный граф без циклов называется {свободнъш) деревом. Граф бе циклов называется ациклическим, или лесом. Таким образом, компонентами связности леса являются деревья. На рис. 5.20, а) и б) приведены два графа; первый из них является деревом, а второй - лесом. а) в) Рис. 5.20 ® @ ф ® г)