Ընդարձակ ենթագրաֆը ենթագիր է, որը պարունակում է բնօրինակ գրաֆիկի բոլոր գագաթները: Ընդարձակ ծառը ընդգրկող ենթագրաֆ է, որը հաճախ հետաքրքրություն է առաջացնում: Գրաֆիկի բոլոր գագաթները պարունակող ցիկլը կկոչվի ընդգրկող ցիկլ:
Քանի՞ ընդարձակ ենթագրաֆ կա:
Կա 2n ինդուկտիվ ենթագրաֆներ (գագաթների բոլոր ենթաբազմությունները) և 2մ ընդգրկող ենթագրաֆներ (եզրերի բոլոր ենթաբազմությունները):
Ինչպե՞ս կարող եմ գտնել ընդարձակ ենթագրաֆ:
Եվ ըստ գրաֆիկի Spanning subgraph-ի սահմանման, G-ն ենթագրաֆ է, որը ստացվում է միայն եզրերի ջնջմամբ: Եթե եզրերի ենթաբազմություններ կազմենք՝ ջնջելով մեկ եզր, երկու եզր, երեք եզր և այլն։ Քանի որ կան m եզրեր, այնպես էլ կան 2^m ենթաբազմություններ: Հետևաբար G-ն ունի 2^մ ընդգրկող ենթագրաֆներ։
Ի՞նչ է նշանակում ծածկված ծառ ասելով:
Գրաֆիկի (G) ընդգրկող ծառը Գ-ի ենթաբազմություն է, որն ընդգրկում է նրա բոլոր գագաթները՝ օգտագործելով եզրերի նվազագույն թիվը: Ընդարձակ ծառի որոշ հատկություններ կարելի է եզրակացնել այս սահմանումից. Քանի որ «տարածվող ծառը ծածկում է բոլոր գագաթները», այն չի կարող անջատվել:
Ի՞նչ է ընդգրկող գրաֆիկի տեսությունը:
Ընդարձակվող ծառը G գրաֆիկի ենթաբազմություն է, որը ունի բոլոր գագաթները ծածկված նվազագույն հնարավոր թվով եզրերով: Հետևաբար, տարածվող ծառը չունի ցիկլեր և այն չի կարող անջատվել: Այս սահմանմամբ մենք կարող ենք եզրակացություն անել, որ յուրաքանչյուր միացված և չուղղորդված գրաֆիկ G-ն ունի առնվազն մեկ տարածվող ծառ:
