ЧИСЛО ДВУХПОЛЮСНЫХ ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНЫХ СЕТЕЙ

Одна из первых попыток описать все электрические схемы, удовлетворяющие некоторым определенным условиям, была сделана в 1892 г. П. А. Мак-Магоном, который исследовал комбинации сопротивлений при последовательном и параллельном соединении и дал без доказательства формулу производящей функции, по которой может быть определено число таких комбинаций, и таблицу чисел таких комбинаций из 10 или менее элементов.

Параллельно-последовательные комбинации не исчерпывают всех возможных сетей, так как они исключают мостиковые соединения типа мостика Уитстона, но в силу своей простоты они представляют собой важный подкласс. Если число элементов меньше 5, все сети являются параллельно-последовательными; для 5 имеется одна сеть мостикового типа — мостик Уитстона; при возрастании числа элементов число сетей мостикового типа растет быстрее, чем параллельно-последовательных, так, например, при 9 элементах мостиковые сети составляют около 40% от всех сетей. Из этого можно заключить (и установлено, что это верно), что для большого числа элементов параллельно-последовательные сети составляют относительно малую часть всех сетей. Тем не менее проблема описания всех сетей настолько трудна, что подробное изучение параллельно-последовательных

сетей желательно по тем соображениям, что даже слабый свет лучше, чем темнота.

Кроме этого, параллельно-последовательные сети интересны сами по себе в другом отношении, а именно в связи с синтезом релейных и переключательных схем, где важно знать, сколько элементов требуется для реализации произвольной переключательной функции от переменных, т. е. число такое, что каждая из различных функций может быть реализована с элементами и по крайней мере одна не может быть реализована с меньшим числом элементов. Верхняя оценка для числа двухполюсных схем с В ребрами определяет нижнюю оценку для так как число различных схем с контактами (с учетом приписывания ребрам символов переменных) должно быть не меньше ; т. е. должно быть достаточно схем для реализации всех функций. Этот общий факт остается верным, если ограничиться только классом параллельно-последовательных схем, и поскольку переключательные схемы наиболее просто реализуются именно в такой форме, определение необходимого для этого числа элементов представляет непосредственный интерес.

Эти соображения заставили нас разобрать доказательство теоремы Мак-Магона о производящей функции, которое полностью приводится ниже, разработать рекуррентные соотношения и схемы подсчета и с их помощью дополнить таблицу Мак-Магона, исследовать поведение числа параллельно-последовательных сетей при большом числе элементов и, наконец, применить это к переключательным функциям, упомянутым выше. Эти вопросы изложены в отдельных пунктах.