Caterpillar ағашы - Caterpillar tree

Шынжыр табан

Жылы графтар теориясы, а құрт немесе шынжыр ағаш Бұл ағаш онда барлық шыңдар орталық жолдан 1 қашықтықта орналасқан.

Caterpillars алғаш рет Гарари мен Швенктің бірқатар жұмыстарында зерттелген. Атау ұсынылды Хоббс.[1][2] Қалай Харари және Швенк (1973) «шынжыр табан - бұл соңғы нүктелерін алып тастаған кезде метаморфоздар түзетін ағаш».[1]

Эквивалентті сипаттамалар

Келесі сипаттамалардың барлығы шынжыр ағаштарын сипаттайды:

  • Олар ағаштар, олар үшін жапырақтары мен құлаған шеттерін алып тастайтын а пайда болады жол сызбасы.[2][3]
  • Олар екі немесе одан да көп деңгейлі шыңдарды қамтитын жол бар ағаштар.
  • Олар кем дегенде үш шыңында ең көп дегенде екі жапырақсыз көрші болатын ағаштар.
  • Олар тармақтың әр шетін ауыстыру арқылы құрылған графигін субграф ретінде қамтымайтын ағаштар жұлдыз графигі Қ1,3 ұзындығы екі жолмен.[3]
  • Олар болуы мүмкін байланысты графиктер сызылған олардың шыңдары екі параллель түзулерде, шеттері қиылыспайтын сызық сегменттері ретінде ұсынылған, әр түзуде бір соңғы нүкте болады.[3][4]
  • Олар кімнің ағаштары шаршы Бұл Гамильтон графигі. Яғни, шынжыр табанда барлық төбелердің циклдік тізбегі бар, олардағы кез-келген тізбектегі төбелердің әр жұбы бір-бірінен бір-екі қашықтықта орналасқан, ал шынжыр табан емес ағаштар мұндай реттілікке ие емес. Осы типтегі циклды параллель екі түзу бойымен шынжыр табанын салу және бір түзудегі шыңдар тізбегін екінші жолдағы реттіліктің керісінше қосу арқылы алуға болады.[3]
  • Олар кімнің ағаштары сызықтық графиктер құрамында а Гамильтондық жол; мұндай жолды ағаштың екі сызықты сызбасында жиектерді ретке келтіру арқылы алуға болады. Жалпы алғанда, ерікті ағаштың сызықтық графигіне Гамильтон жолын (оның өлшемі) қосатындай етіп қосу керек шеттер саны Гамильтондық аяқтау ) ағаш жиектері ыдырауы мүмкін жиек-доғал тәрізді шынжыр табандардың ең аз санына тең.[5]
  • Олар байланысты графиктер жол ені бір.[6]
  • Олар байланысты үшбұрышсыз аралық графиктер.[7]

Жалпылау

A к-ағаш Бұл аккордтық график дәл nк максималды клиптер, әрқайсысы бар к + 1 төбелер; ішінде к- өзі емес ағаш а (к + 1) -клика, әрбір максималды клик графикті екі немесе одан да көп компоненттерге бөледі немесе оның құрамында жалғыз жапырақ шыңы, шыңы тек жалғыз максималды кликке жатады. A к- жол а к- ең көп дегенде екі жапырақтан тұратын ағаш және а к-қатерпиллар - а к-ке бөлуге болатын ағаш к-жол және кейбір к- жапырақтары, әрқайсысы а бөлгіш к-кликасы к-жол. Бұл терминологияда 1-құрт шынжыр табанмен бірдей, және к-қатерпиллар - бұл жиек-максималды графиктер жол ені к.[6]

A лобстер график - а ағаш онда барлық шыңдар центрден 2 қашықтықта орналасқан жол.[8]

Санақ

Caterpillars сирек кездесетіндердің бірін ұсынады графикалық санау нақты формула беруге болатын мәселелер: қашан n ≥ 3, бар шынжыр табандар саны n белгісіз шыңдар [1]

Үшін n = 1, 2, 3, ... сандарының n-vertex шынжыр табандары

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (реттілік A005418 ішінде OEIS ).

Есептеудің күрделілігі

Графиктен созылып жатқан шынжыр табанды табуға болады NP аяқталды. Байланысты оңтайландыру проблемасы - бұл графиктің шектерінде қосарланған шығындар бар және мақсаты кіріс графигін қамтитын және ең аз жалпы шығындарға ие болатын шынжыр табанды ағашты табу болып табылатын Минималды созылатын Caterpillar проблемасы (MSCP). Мұнда шынжыр табанның құны оның шеттерінің шығындарының қосындысы ретінде анықталады, мұнда әр шеті жапырақ немесе ішкі бөлігі ретіндегі рөліне байланысты екі шығынның бірін алады. F (n) - жоқжуықтау алгоритмі егер MSCP үшін болмаса P = NP. Мұндағы f (n) - кез-келген полиномдық уақыт бойынша есептелетін функция, графиктің төбелерінің саны.[9]

Шектелгенде MSCP үшін оңтайлы шешім табатын параметрленген алгоритм бар кеңдік графиктер. Сонымен, Spanning Caterpillar есебінде де, MSCP-де де сызықтық уақыт алгоритмдері болады, егер график сыртқы жазықтық, қатар параллель немесе Галин графигі.[9]

Қолданбалар

Caterpillar ағаштары қолданылған химиялық графика теориясы құрылымын ұсыну бензиноид көмірсутегі молекулалар. Бұл көріністе бір мысық құрылады, оның әр шеті молекулалық құрылымдағы 6-көміртекті сақинаға сәйкес келеді, ал сәйкес сақиналар ұшынан ұшына жалғасқан сақиналар тізбегіне тиесілі болған сайын екі шеті төбеге түседі. құрылым. Эль-Базиль (1987) былай деп жазады: «Қазір» химиялық графика теориясы «деп аталатын жерде маңызды рөл атқарған графиктердің барлығы дерлік шынжыр ағаштарымен байланысты болуы ғажап». Бұл тұрғыда шынжыр ағаштар ретінде белгілі бензеноид ағаштары және Гутман ағаштары, Иван Гутманның осы саладағы жұмысынан кейін.[2][10][11]

Әдебиеттер тізімі

  1. ^ а б в Харари, Фрэнк; Швенк, Аллен Дж. (1973), «Шынжыр табандар саны» (PDF), Дискретті математика, 6 (4): 359–365, дои:10.1016 / 0012-365x (73) 90067-8.
  2. ^ а б в Эль-Базиль, Шериф (1987), «Шынжыр табандарының химия мен физикада қолданылуы», Математикалық химия журналы, 1 (2): 153–174, дои:10.1007 / BF01205666.
  3. ^ а б в г. Харари, Фрэнк; Швенк, Аллен Дж. (1971), «Гамильтон алаңымен ағаштар», Математика, 18: 138–140, дои:10.1112 / S0025579300008494, hdl:2027.42/153141.
  4. ^ Харари, Фрэнк; Швенк, Аллен Дж. (1972), «Екі жақты графиктердің жаңа қиылысу нөмірі», Utilitas математикасы., 1: 203–209.
  5. ^ Райчаудхури, Арундхати (1995), «Ағаштың жалпы аралық саны және оның сызықтық графигінің Гамильтондық аяқталған нөмірі», Ақпаратты өңдеу хаттары, 56 (6): 299–306, дои:10.1016/0020-0190(95)00163-8.
  6. ^ а б Проскуровский, Анджей; Телле, Ян Арне (1999), «Аралық модельдері шектеулі графиктер кластары» (PDF), Дискретті математика және теориялық информатика, 3: 167–176, мұрағатталған түпнұсқа (PDF) 2011-06-06, алынды 2010-05-07.
  7. ^ Экхофф, Юрген (1993), «Аралық графиктер», Графикалық теория журналы, 17 (1): 117–127, дои:10.1002 / jgt.3190170112.
  8. ^ Вайсштейн, Эрик В. «Омар графигі». MathWorld.
  9. ^ а б Хосравани, Масуд (2011). Жалпы оңтайлы шынжыр табандарды және шекара сызықтарын іздеу (Ph.D.). Окленд университеті.
  10. ^ Гутман, Иван (1977), «Бензеноидты жүйелердің топологиялық қасиеттері», Теоретика Химика Акта, 45 (4): 309–315, дои:10.1007 / BF00554539.
  11. ^ Эль-Базиль, Шериф (1990), «Катерпиллар (Гутман) ағаштары химиялық графика теориясында», Гутман, I .; Cyvin, S. J. (ред.), Бензеноидты көмірсутектер теориясының жетістіктері, Ағымдағы химияның тақырыптары, 153, 273–289 б., дои:10.1007/3-540-51505-4_28.

Сыртқы сілтемелер