Пређи на садржај

Туранов граф

С Википедије, слободне енциклопедије

Туранов граф T(н,р) је комплетни мултипартитни граф сачињен дељењем сета н темена на р подсетова, са величинама које су што је више могуће једнаке, и повезују два темена ивицом кад год припадају различитим подсетовима. Граф ће имати (н мод р) подсетова величине [н/р], и р - (н мод р) подсетова величине [н/р]. То је комплетан р-партитан граф

Svako teme ima stepen ili n-[n/r] ili n-[n/r]. Broj ivica je:

То је регуларан граф, ако је н дељиво с р.

Туранова теорема

[уреди | уреди извор]

Туранови графови су добили назив по Пал Турану, који их је користио како би доказао Туранову теорему, важан резултат у екстремалној теорији графова.

По принципу голубље рупе, сваки сет од р+1 темена у Турановом графу укључује два темена на истој партицији подсета; дакле, Туранов граф не садржи клику величине р+1. Према Турановој теореми, Туранов граф има највећи могући број ивица од свих (р+1)-графова без клика са н темена. Кеваш и Судаков (2003) су показали да је Туранов граф такође једини (р+1)-граф без клика реда н у коме сваки подсет од αн темена покрива најмање  {\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2} ивица, ако је α довољно близу 1. 

Ердос-Стоунова теорема наслеђује Туранову теорему спајајући број ивица у графу које немају фиксиран Туранов граф као подграф. Преко ове теореме, сличне везе у екстремалној теорији графова могу бити доказане за било који искључени подграф, у зависности од хроматског броја подграфа.

Посебни случајеви

[уреди | уреди извор]
The octahedron, a cross polytope whose edges and vertices form a Turán graph T(6,3).

Неколико избора параметра р у Турановом Графу доводи до нотабилних графова који се независно проучавају.

Туранов граф T(2н,н) може бити формиран уклањањем савршено одговарајућих од а комплетног графа K2n. Како је Робертс (1969) показао, овај граф је такође 1-скелетон од н-димензионалног унакрс-политопа; на пример, граф Т(6,3) = к2,2,2 је октаедрални граф, граф регуларног октаедра. ако н парова оду на журку а, и свака особа се рукује са сваком особом осим са својим партнером, онда овај граф описује сет руковања која су се одиграла; из овог разлога такође се назива и коктел журка граф.

Туранов граф Т(н,2) је комплетан бипартитни граф и, када је н једнако, Муров граф. Када је р делилац од н, Туранов граф је симетричан и строго регуларан, иако неки аутори сматрају Туранове графове тривијалним случајевима строге регуларности и даље их искључују из дефиниције строго регуларног графа.

Туранов граф  има 3a2b максималних кликова, где 3a + 2b = n и b ≤ 2; сваки максимални клик се формира бирањем једног темена из сваке партиције подсета. Ово је највећи могући број максималних кликова међу свим n-теменим графовима независно од броја ивица у графу (Мун и Мозер 1965); ови графови се понекад називају Мун-Мозерови графови.

Остале особине

[уреди | уреди извор]

Сваки Туранов граф је кограф; може бити формиран од индивидуалних темена од стране секвенци дисјунктних унија и комплементних операција. Специфично, таква секвенца може почети формирањем сваког од независних сетова Турановог графа као дисјунктна унија изолованих темена. Тада, укупни граф је комплемент дисјунктних унија комплемената ових независних сетова.

Чао и Новацки (1982) показују да су Туранови графови хроматично јединствени: ниједни други графови немају истие хроматске полиномијале. Никифоров (2005) користи Туранове графове да снабде доњу границу суме  kте својствене вредности графа и његовог комплемента.

Фалс, Павел, и Сноејинк су развили ефикасан алгоритам за налжење кластера ортологних група гена у геномним подацима, представљањем података као граф и и тражењем великих Туранових подграфова.

Туранови графови такође имају неке интересантне особине повезане са геометријском теоријом графова. Пор и Вуд (2005) су пронашли нижу границу од Ω((rn)3/4) на запремини било ког три-димензионалног, са уграђеном мрежом, Турановог графа. Витсенхаусен (1974) претпоставља да је максимална сума од квадратних дистанци, међу n тачака са јединичним пречником у Rd, је постигнут за конфигурацијом формираном уградњом Турановог графа на темена регуларног симплекса.

Н-темени граф G је подграф Турановог графа T(n,r) ако и само ако G признаје праведно бојење са r боја. Партиција Турановог графа у независним сетовима кореспондира партицији G у класе боја. Нарочито, Туранов граф је јединствен масимални n-темени граф са  r-боја праведно обојених.

Литература

[уреди | уреди извор]

Спољашње везе

[уреди | уреди извор]