• Чему нас может научить теорема о четырех красках в разработке ПО

    • Translation
    Теорема о четырёх красках — это математическая формулировка, связанная с картами. Все примеры карт, которые я нашёл в Интернете, были слишком сложными для введения, поэтому я набросал собственный неказистый рисунок:


    Если посмотреть под другим углом, то можно воспринимать её как граф — достаточно ужать все области до кругов и соединить круги, соответствующие соседним областям карты:


    Теорема о четырёх цветах утверждает, что для разметки любого рисунка, похожего на мой, (или соответствующего ему графа) достаточно четырёх цветов, чтобы никакие соседние области не имели одинаковой раскраски. Это значит, что если мы возьмём карту США или Европы, даже со всеми этими причудливыми границами, и присвоим каждому штату или стране свой цвет, то для разметки всей карты будет достаточно четырёх цветов.

    Некоторым картам не нужны все четыре цвета, им достаточно всего двух или трёх. Карта, которую можно раскрасить одним цветом, будет не очень интересной, так что её мы пропустим.

    Первое, что поразило меня, как разработчика ПО: четыре цвета — это совсем мало. Кажется поразительным, что любой граф можно раскрасить всего четырьмя цветами; мне кажется, что если я нарисую графы некоторых из кодовых баз, с которыми я работал, где рёбрами будут соединены обменивающиеся данными объекты, то им запросто может потребоваться дюжина цветов.
    Читать дальше →