График теориясында ағаш - бұл бағытсыз граф, онда кез келген екі төбелер бір жол арқылы қосылған немесе эквивалентті түрде қосылған циклдік бағытталмаған граф. … Көп орман (немесе бағытталған орман немесе бағдарланған орман) – негізгі бағытталмаған графигі орман болатын бағытталған ациклді граф.
Бағытталған және бағытталмаған ағаштар дегеніміз не?
Циклдері жоқ бағытталмаған график орман, ал егер ол қосылған болса, ол ағаш деп аталады. Бағытталған график орман (немесе ағаш) болып табылады, егер барлық жиектер бағытталмаған жиектерге түрленсе, ол бағытталмаған орман (немесе ағаш) болса. Тамырлы ағаш – бір төбесі түбір ретінде белгіленген ағаш.
Ағаштар неге бағытталмаған?
Теорема: Егер әр жұп шыңдар арасында дәл бір қарапайым жол болса бағытысыз график ағаш болып табыладыДәлелдеу: Егер бізде ағаш болып табылатын T графигі болса, онда ол циклсыз қосылуы керек. T қосылғандықтан, әрбір шыңдар жұбының арасында кемінде бір қарапайым жол болуы керек.
Бағытталған ағаш деген нені білдіреді?
Бағытталған ағаш ациклді бағытталған график Оның 1-дәрежесі бар бір түйіні бар, ал қалған барлық түйіндердің суретте көрсетілгендей 1-дәрежесі бар: Шектеу дәрежесі 0 болатын түйін сыртқы түйін немесе терминалдық түйін немесе жапырақ деп аталады. Бірден үлкен немесе тең шегі бар түйіндер ішкі түйін деп аталады.
Бағыты жоқ графиктің ағаш екенін қалай анықтауға болады?
Бағыты жоқ графиктер жағдайында біз үш қадамды орындаймыз:
- Әр түйінде дәл бір ата-анасы бар екеніне көз жеткізу үшін кез келген түйіннен DFS тексеруін орындаңыз. Олай болмаса, қайтарыңыз.
- Барлық түйіндерге кіргенін тексеріңіз. DFS тексеруі барлық түйіндерге кіре алмаса, қайтарыңыз.
- Әйтпесе, график ағаш болып табылады.
