Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану


Ағаштар және орман. Ағаштардың қасиеттері



бет15/30
Дата23.12.2021
өлшемі0,66 Mb.
#127967
1   ...   11   12   13   14   15   16   17   18   ...   30
Байланысты:
darismatlogidm

2.Ағаштар және орман. Ағаштардың қасиеттері

 

Циклсіз байланысқан графты ағаш дейміз. Басқаша айтқанда барлық қырлары ациклділік болатын графты ағаш дейміз. Төмендегі төрт шартты қанағаттандыратын графты ағаш дейміз:



  1. Кез келген қырды алып тастағанда байланысты граф байланыспайтын болады.

  2. Қырлар саны төбелер санынан біреуі аз болатын байланысты граф.

  3. Бір элементарлық тізбекте байланыста болатын граф.

  4. Екі төбені байланыстыратын қырларды қосқаннан кейін пайда болған циклсіз граф.

Егер граф қисынды бола тұрып, оның циклі болмаса, онда граф ағаш  деп  аталады.

Егер графтың қисынды компоненттері ағаш болса, онда граф орман деп  аталады. Көбінесе ағашта түйін мен қосымша қабырғалар болмайды.

Графтың тек бір қабырғасына ғана инцидентті төбені соңғы  (немесе аспалы)төбе деп атайды,ал  соңғы  нүктеге инцидентті қабырғаны  графтың  соңғы графы деп атаймыз.

1-суретте көрсетілген G1және G2 графтары –ағаш болып табылады, ал G3графы ағаш емес.

 

1-сурет


 



Достарыңызбен бөлісу:
1   ...   11   12   13   14   15   16   17   18   ...   30




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет