Արդյո՞ք յուրաքանչյուր ծառ երկմասնի՞ գրաֆիկ է:

2024 Հեղինակ: Fiona Howard | [email protected]. Վերջին փոփոխված: 2024-01-10 06:38

Յուրաքանչյուր ծառ երկկողմանի է: Զույգ թվով գագաթներով ցիկլային գրաֆիկները երկկողմանի են: Յուրաքանչյուր հարթ գրաֆիկ, որի բոլոր երեսներն ունեն զույգ երկարություն, երկկողմանի է:

Բոլորը երկմաս գծապատկերները ծառե՞ր են:

Յուրաքանչյուր ծառ երկկողմանի է: Զույգ թվով գագաթներով ցիկլային գրաֆիկները երկկողմանի են: Յուրաքանչյուր հարթ գրաֆիկ, որի բոլոր դեմքերը հավասար երկարություն ունեն, երկմասն է:

Ինչու յուրաքանչյուր ծառ երկմաս գրաֆիկ է:

Ծառ. Ծառը N – 1 եզրերով պարզ գրաֆիկ է, որտեղ N-ն այնպիսի գագաթների թիվն է, որ երկու գագաթների միջև կա ուղիղ մեկ ճանապարհ: Երկկողմ. Գրաֆիկը երկկողմանի է եթե մենք կարող ենք գագաթները բաժանել երկու տարանջատված բազմությունների V1, V2 այնպես, որ ոչ մի եզր չի միացնում գագաթները նույն բազմությունից

Ինչպե՞ս եք ապացուցում, որ յուրաքանչյուր ծառ երկմաս գրաֆիկ է:

Թող լինի''-ով նշված գագաթների բազմությունը և լինի ''-ով նշված գագաթների բազմությունը: Ակնհայտ է, որ ցանկացած երկու տարբեր գագաթներ հարևան չեն եզրով, և նույնպես, քանի որ ծառերը շղթա չունեն. Ավելին, հստակորեն բաժանեք գծապատկերի գագաթային բազմությունը երկու տարանջատված ենթաբազմությունների: Այսպիսով, ցանկացած ծառ երկկողմանի է:

Արդյո՞ք յուրաքանչյուր ամբողջական գրաֆիկ երկմասնակա՞ն է:

Յուրաքանչյուր ամբողջական երկմաս գրաֆիկ: K , -ը Մուրի գրաֆիկ է և (n, 4)-վանդակ: Ամբողջական երկմաս գծապատկերներ K , և K , _{+1 ունեն առավելագույն հնարավոր թվով եզրեր բոլոր եռանկյունից զերծ գծապատկերների մեջ՝ նույն թվով գագաթներով; սա Մանթելի թեորեմն է։}