Заранкевич проблемасы-жазықтықта толық екі бұрышты баған бейнеленген қиылыстардың ең аз санын табумен байланысты графтар теориясының есебі.[1]

Сондай-ақ, Тұранның кірпіш зауыты (ағылш. Tyran ‘ s brickfactory problem) — Екінші дүниежүзілік соғыс кезінде кірпіш фабрикасында жұмыс істей отырып, осы тапсырманы тұжырымдаған венгр математигі Пала Туранның құрметіне.

Поляк математиктері Казимежем Заранкевич (Польша. Kazimierz Zarankiewicz) гипотеза айтылған, графтың кейбір қарапайым бейнесі қиылысудың ең аз саны бар, алайда, жеке жағдайларды қоспағанда, оның оңтайлылығы дәлелденбеген болып қалады.[2]

Шығу тегі және тұжырымы
Екінші дүниежүзілік соғыс кезінде венгерлік математик Пал Тұран кірпіш фабрикасына мәжбүрлі жұмысқа жіберілді, онда ол пештен кірпіштері бар вагоншаларды қоймаға шығарды. Зауытта кез-келген пеш пен кез-келген қойма арасында темір жол төселді, бұл ретте вагонетканы осы жолдар қиылысқан жерде итеру қиын болды. Бұл Туранды қиылысу санын азайту үшін жолды қалай қайта салу туралы сұраққа шабыттандырды. [1]

Математика тұрғысынан бұл графтың жазықтықтағы бейнесінің есебі: пештер мен қоймалар бағанның жоғарғы жағын, ал темір жолдар — оның қабырғаларын қояды. Әрбір пеш пен әрбір қойма арасында дәл бір жол салынғандықтан, мұндай баған толық екі жақты. Егер пештер p, ал қоймалар s болса,онда мұндай бағандар {\displaystyle K_{p,s}} {\displaystyle K_{p, s}} белгіленеді. Туран проблемасы {\displaystyle K_{p,s}} {\displaystyle K_{p,s}} {\displaystyle K_ {p, s}}} бағанының жоғарғы және қабырғаларын жазықтықта орналастыру үшін, оның ұшына жатпайтын, және де баған қабырғаларында шыңдардан ерекшеленетін қиылыстардың ең аз саны болуы тиіс. Бұл ретте қабырға міндетті түрде тік сызықты болмауы керек, бірақ ең аз деп болжанатын шешімде бұл солай.[2]

Туран мәселесі графтар қиылыстарының ең аз саны туралы бірінші міндеттердің бірі болып саналады.[3] жеке жағдай “үйлер мен құдықтардың” классикалық математикалық міндеті болып табылады, онда пештер мен қоймалардың рөлін үйлер мен құдықтар ойнайды, әрқайсысы — үш данадан.

Шешім әрекеті
Заранкевич және Казимеж Урбаник (поляк. Kazimierz Urbanik) 1952 жылы Польшадағы Туранның баяндамаларына қатысты.[5]

Екі жағдайда да олар толық екі жақты бағандарды мынадай түрде салуды ұсынды (баптың басында суретті қараңыз): тік осьтің бойымен бір түсті (“пештер”), екінші түсті жоғарғы (“қоймалар”) — көлденең осьтің бойымен, ал осьтердің қиылысу нүктесін әр жағынан тең (егер осы түстің шыңы жұп болса) немесе тең (егер олар тақ болса) болатындай етіп таңдау. Нәтижесінде екеуі де қабырға баған үшін келесі қиылыстар санын алды:

{\displaystyle {\biggl \lfloor }{\frac {n}{2} {\biggr \rfloor} {\biggl \lfloor} {\frac {n-1} {2} {\biggr \rfloor} {\biggl \lfloor} {\frac {m} {2} {\biggr \rfloor} {\biggl \biggl\lfloor} {\biggl \lfloor} {\frac{M-1} {2}} {\biggr \ rfloor}.{\biggl\lfloor} {\frac {n-1} {2} {\biggr\rfloor} {\biggl\lfloor} {\frac {n-1} {2} {\biggr\rfloor} {\biggl\lfloor} {\frac {m} {2} {\biggr\rfloor} {\biggl\biggl \lfloor} {\frac {m} {2} {\biggr \rfloor} {\biggl \ rfloor} {\biggl \ lfloor} {\frac {M-1} {2}} {\biggr \ rfloor}.}
Бұл мысал жоғарыдан қиылысулар санына шектеу береді, алайда төменгі жағынан шектеу беретін оның минималдылығының екі дәлелі қате болып шықты: олар Герхард Рингельмен және Пол Кайненмен (ағылш. Paul Kainen) 1965 жылы дерлік]

Жалпы жағдайда ең төменгі мәселе әлі де гипотеза болып қалса да, жеке жағдайлар сәтті дәлелденді: {\displaystyle K_{p,S}} {\displaystyle K_{p,s}} {\displaystyle K_ {p, s}}} {\displaystyle P\leqslant 3} {\displaystyle p\leqslant 3} {\leqslant 3} {\displaystyle P\leqslant 3} {\displaystyle K_ кейінірек {\displaystyle K_ {p,s}}} {\displaystyle K_ {\displaystyle K_ {p,s}}} {, S} {\displaystyle P \ leqslant 6} {\displaystyle P \ leqslant 6} кезінде.[7] кез келген екі p үшін, s минималдылықтың дәлелі тексерулердің соңғы санын талап ететіндіктен, ол жеткілікті аз p, s кезінде өндірілген.[8] сондай-ақ дәлелденген, қиылыстардың ең аз саны Заранкевичтің бағалауынан кем дегенде 83% құрайды.[9]