Негізгі анықтамалар
жүктеу/скачать 289,71 Kb.
|
13-15АПТАдәрістері
| Бихроматикалық граф (Кениг графы, екі бөлікті граф) 2–хроматикалы граф а) графта тақ ұзындықты цикл болмайды, б) графтың төбелер жиынын Xi-дің бір ғана жағынан алынған кез-келген екі төбесі өзара сыбайлас емес болатындай, Х1 және Х2 деп екі бөлікке бөлуге болады деген екі қағидаларға эквивалентті болады. Граф толық бихроматикалық (толық екі бөлікті граф) деп аталады, егер оның әртүрлі бөліктерінен алынған кез-келген төбелері – сыбайлас болса. Белгіленуі: Km,n, мұндағы, m=|X1|, n=|X2|, мұнда қабырғалар саны mn-ге тең болады.
Көп полюсті желі деп –төбелері белгіленіп көрсетілген орграфты айтамыз. Екі полюсті желі деп – екі белгіленіп көрсетілген төбелері бар желіні айтамыз. Әлді байланысты орграф (әлді орграф) деп кез-келген екі төбелерінен бір-біріне бағыт бойымен (қабырға бойымен) жетуге болса. Біржақты байланысты орграф (Біржақты орграф) бұл – кез-келген төбелер жұбы біржақты байланысты болатын, яғни кез-келген төбеден қалған төбелерге қабырға бағытымен, ал кері жол болмауы да мүмкін. Әлсіз байламды орграф (әлсіз орграф) деп доғасының бағдарын өзгерткен соң байланысты болып қалатын орграфты айтамыз. k-байланысқан граф (k-төбелі байланысқан граф) деп кез-келген k-1 төбесін жойған соң, байланысты болып қалатын графты айтамыз. k-қабырғалы- байланысқан граф деп кез-келген k-1 қабырғасын жойған соң, байланысты болып қалатын графты айтамыз. Біртекті (реттелетін k-реттелуші) граф деп барлық төбелерінің дәрежелері бірдей k-ға тең болатын графты айтамыз. (n, m)-граф деп – нақты n төбесі бар, m қабырғасы бар графты айтамыз. Қосымша граф ~G графы – G графында қанша төбелер жиыны болса, сонша төбелер жиыны бар граф және ~G-дың екі төбесі сыбайлас болады, сонда және тек қана сонда егер осы төбелер G-да сыбайлас болмаса. жүктеу/скачать 289,71 Kb. Достарыңызбен бөлісу:
|