Пример.
: :
гомеоморфен .
Понтрягин-Куратов теоремасы (планарлықтың критериі):
Граф планар болады сонда тек сонда егер оның ішкі графтары гомеоморфты графтарынан тұрмаса және .
(дәлелдеусіз)
Есеп: Ешбір картада бір-бірімен шектеспейтін 5 жұп ел табылмайтын дәлелдеңдер.
Графтың төбелік бояуы
Ескерту. Графтар теориясында графтарды бояу маңызды орын алады. Бұндай есептерге практикалық есептерден көбісі келіп тіркеледі.
Анықтама. Графтың төбелік бояуы деп графтың әрбір төбесіне белгілі бір түспен (номермен) белгілесе.
Анықтама. Егер бір төбеге инцидент болатын ешқандай екі төбе бір түске боялмаса, онда графтың қабырғалық бояуы дұрыс деп аталады.
Анықтама. Графтардың төбелік дұрыс бояуына ең аз түстің саны кететін осы графтың хроматикалық индексі деп аталады және былай белгіленеді .
Дата добавления: 2015-09-27 | Просмотры: 739 | Нарушение авторских прав
|