Дискретная математика

171 32. При каких числах питв графе существует эйлеров цикл? 33. Пусть граф состоит из вершин и ребер тетраэдра. Будет ли он пленарным? 34. Пусть граф состоит из вершин и ребер куба. Будет ли он планариым? 35. Является ли планарньш граф граф К2.3; граф Кзу, граф 36. Является ли планарньш граф К/, граф Ks; граф 37. Постройте все неизоморфные деревья; с 4 вершинами; 5 вершинами; 6 вершинами. 38. Постройте все неизоморфные ордеревья: с 3 вершинами; 4 вершинами. 39. Сколько ребер нужно отбросить в графе К„,„, чтобы получить остовное дерево? 40. В графе Кз ; введите длины ребер так, чтобы любые два ребра имели различные длины. Постройте остовное дерево, сумма длин ребер которого наименьшая из возможных. 41. Требуется оповестить всех членов садоводческого общества о собрании. Пусть на один телефонный звонок требуется одна минута. Положим, что каждый оповещённый сразу последовательно звонит двум ещё не оповещённым членам садоводческого общества. Положим также, что все телефоны в нужный момент свободны и работают, а члены рассматриваемого общества оказываются у телефонов. В начальный момент председатель общества звонит двум членам общества (последовательно сначала одному, затем другому, тратя по одной минуте). Каждый, подучивший известие, поступает также, как и председатель, оповещая двух неоповещённых. Сколько времени потребуется, чтобы оповестить: а) 600 человек? б) 3000000 (три миллиона) человек? С только новых человек будут узнавать о собрании на к-й минуте после начала оповещения? Указание: построить дерево оповещения, обращая внимание на уровни дерева и на то, что рёбра дерева имеют различную длину. 42. Члены клуба «Арстраы» проводят регулярные встречи через равные промежутки времени. Каждый человек, вступающий в клуб «Арстран», должен внести взнос в сумме 26 400 рублей. После этого он получает статус партнёра 1-й степени и имеет право приглашать на встречи по одному гостю - будущему партнёру клуба. Если А ~ партнёр 1 -й степени лично вовлёк в клуб партнёров Ai, А2, A3, Л4,..., AN, N >2, (т.е. более двух новых партнёров), то он считается партнёром 2-й степени для членов ЛЗ, A4,...,AN. Для А{ к А2 он (партнёр А) является партнёром 1-й степени. Если А\ или Л2 вовлёк в клуб партнёра С, то А является партнёром 2-й степени для С. Распределение взносов в клубе осуществляется следующим образом. Если В приглашен партнёром 1-й степени, то взнос партнёра В распределяется: - 4 ОО рублей получает В\ - его пригласитель (партнёр 1-й степени);