Ի՞նչ է նշանակում գրաֆիկի երկկողմանի լինելը:

2024 Հեղինակ: Miles Stephen | [email protected]. Վերջին փոփոխված: 2023-12-15 23:37

-ի մաթեմատիկական ոլորտում գրաֆիկ տեսություն, ա երկկողմանի գրաֆիկ (կամ բիգրաֆը) ա գրաֆիկ որի գագաթները կարելի է բաժանել երկու անհամապատասխան և անկախ բազմությունների, և այնպես, որ յուրաքանչյուր ծայրը միացնում է գագաթը դեպի մեկ ին: Vertex հավաքածուներ և. սովորաբար կոչվում են մասեր գրաֆիկ.

Այնուհետև ինչպե՞ս եք իմանում, որ գրաֆիկը երկկողմանի է:

Այսպիսով եթե դուք կարող եք 2-գույն ձեր գրաֆիկ , դա կլինի երկկողմ . Ակնհայտորեն, եթե դուք ունեք եռանկյուն, այն գունավորելու համար անհրաժեշտ է 3 գույն: Երբ դուք ունեք 2 գունավորում, երկու գունային դասեր (կարմիր գագաթներ, կապույտ գագաթներ), ձեզ տալիս են երկմասնությունը: Ա գրաֆիկը երկկողմանի է, եթե և միայն եթե ներսում տարօրինակ ցիկլ գոյություն չունի գրաֆիկ.

Հետագայում հարց է առաջանում՝ ի՞նչ է նշանակում լինել երկկողմանի։ Ա երկկողմ Գրաֆը այն գրաֆիկն է, որում գրաֆիկական գագաթների բազմությունը կարելի է բաժանել երկու անկախ բազմությունների, և միևնույն բազմության մեջ երկու գրաֆիկական գագաթներ հարևան չեն: Այլ կերպ ասած, երկկողմ գրաֆիկները կարելի է համարել հավասար երկու գունավոր գրաֆիկների:

Բացի այդ, ո՞րն է երկկողմանի գրաֆիկի իմաստը:

Ա երկկողմանի գրաֆիկ , որը նաև կոչվում է բիգրաֆ, մի շարք է գրաֆիկ գագաթները տարրալուծվում են երկու անհամաչափ բազմությունների, այնպես որ երկուսը չկան գրաֆիկ նույն բազմության մեջ գագաթները հարակից են: Ա երկկողմանի գրաֆիկ k-partite-ի հատուկ դեպք է գրաֆիկ հետ։

Կարո՞ղ է ամբողջական գրաֆիկը լինել երկկողմանի:

Ա ամբողջական երկմաս գրաֆիկ է գրաֆիկ որի գագաթները կարող է բաժանել երկու ենթաբազմությունների V₁ և Վ₂ այնպես, որ ոչ մի եզր չունի երկու վերջնակետերը նույն ենթաբազմության մեջ, և բոլոր հնարավոր եզրերը, որոնք կարող էր միացնել vertices տարբեր ենթաբազմությունների մաս է գրաֆիկ.