Home of DISCRETE MATHEMATICS (M 205-HY 118) Problems with Greek fonts? Try going to http://www.csd.uch.gr/~kolount/discrete-vt420.html or even to http://www.csd.uch.gr/~kolount/discrete-latin.html

� ������ ���� ��������� ��� ��������� http://www.csd.uch.gr/~kolount/discrete.html ���� ������ ��� ��� ��������� http://www.math.uiuc.edu/~kolount/discrete.html

�������� �� ��� ������������ ��������������� Netscape, Mosaic, Internet Explorer (���� ����������� ��������� graphics) ���� �� ��������� lynx. ���� ��� ������� graphics ��� �������� �� �� ������� ��� ������ ����������� ��������� �������� �.�. ��� ������
lynx http://www.csd.uch.gr/~kolount/discrete.html

���� ��������� ��� ��� ����� graphics ������� ��������� �� ��������� ��� �� �� ���������� ���� ���� ���������� ����������. �� �������� ���� ���� ������ ��� ������� ������������ ����������� (URL) ��� �� ����� ����� ����������� ��� ��� ��� ������ (������� �� �� �� ��������� �����) �� �������� �� ����� �������� �������� ��� ������.

�� ��� ��������� ������������ ���������� ��� ����� ��� �������.

������������ ������ -- ���������� �����

�������� ���������� (M 205 - �� 118)

������ ������� 1997-98

����: �, �� 2-4 (��� ��)

��������: ������� �. ������������

��������� ������
E-mail: kolount@math.uch.gr
�������: Z 303, ���� ��������: ����������� ����� ���� � �� ��������.
������--����������: �� ���������� ���������� ��� �� ������ C.L. Liu, "�������� ��������� �����������", ��� �� ������������ ������� ��� ��� �����. �������� ������. ����������� �� ���������� ��� ����� ����������.
�� ������ ��� �� ��������� ������������� (���� ��� ������������� ���)
  1. ���������� �������
  2. ������� (enumeration)
  3. ���������� �����������
  4. ����������� �������
  5. ���� ����������-����������� (Inclusion-Exclusion Principle)
  6. ���������, ������
  7. ����� ���������� �� ���������
  8. ������������ ����������

�������� ���'��� �� �������� ��� �������� �� ������� ��� �������� �� 10-15 ��������/��������. ���� 2� ������� ��� ��� 15 ������� ����� �� �������� �� ������� (�� �������� ����������) ��� ������ ��� ���� �������� ��� �� ���������� ��� �� ����������� 2 �������� (� ��� ���� ��������). � ��������� ��� �������� �'���� ����� ����������� ���� ���������� ������ � ��������� ��� ���� �� ������������ (�������, �������) �� ��� ��� ������ �������.

����������� �������: ���� I � ������ ��� �������� ��� �������, M � ������ ��� ������� ��� T � ������ ��� ��������.
� ������� ������ ��� ��� ������� ��� ������� �� ����� �� ������� ���:

  1. I
  2. 0.6 I + 0.4 M
  3. 0.6 I + 0.4 T
��� ��� ������� ����������� � ������� ������ ����� ����� ��� �������� ��� ����.

���� ��������: � ������ ���� �� ������������ ������� ��� ������ ��� ������� �� �������� ���������� (� 205). ��� �� �������� �������:

  1. ��� ���� ������� ��������� ��� �� �������� ���� ���� ��� ������
  2. ����� �������� ������� �� ������ ���, �����������, ���������� ��� �� ���� ����
  3. ����� ������ ���������
  4. ���������� ������������ (����������� �������������, ���������� �������� ��� ��� ��������� ��� ������������, �.�.�.)
  5. ������� (links) �� ����� ������� ��� Internet �� �������� ������
  6. ������� �������� �������� ������� �� �� ������, �.�.
����� ��� ���������� ��� �������� ������ ��� ��� ������ ������������ ����������� �� ��� ����������� ���� ������� ���� ��� �� ������ ��� ��������� �������� ��� �� ����������� �������.

����� � ������;
���� ��� ���� ������ ������� ����� ��� ������� ����� �� ������� ��� ��� �������� ��� �� ������� ���������� ������ ��� Internet. ������ ����� �� �������� ������ �� ������ ����������� ������ �� ���� ��� ������ ����� ��� �� ��� �� ��� ����������.
������, ��� ��� ������� ������ ��� ��� ����� �� ��������� ������� ������� ��� �� ����� �� ���� ����� �� ��� ����������, � ������ ���� �� ��������� ��� �� ��������� ��� ��� �� ������� ��� ������� ��� ���� �� �������, ���� �� ������ ������ �� ����� ��� ��� ���������� ��� ����.

����� � ������;
���� ��� ���� ������ ������� ����� ��� ������� ����� �� ������� ��� ��� �������� ��� �� ������� ���������� ������ ��� Internet. ������ ����� �� �������� ������ �� ������ ����������� ������ �� ���� ��� ������ ����� ��� �� ��� �� ��� ����������.
������, ��� ��� ������� ������ ��� ��� ����� �� ��������� ������� ������� ��� �� ����� �� ���� ����� �� ��� ����������, � ������ ���� �� ��������� ��� �� ��������� ��� ��� �� ������� ��� ������� ��� ���� �� �������, ���� �� ������ ������ �� ����� ��� ��� ���������� ��� ����.

��, 16 ���: �������� ���� ��� ��� ��������� ��� ������� �� ���������� ���������� ��� �� ��� ������������ ���� �� �������.

���� ������� ������� ��� ����������� ������������� �� ���� ������ ��� ���������� �� �������������.

  1. L.O. Katzoff and A.J. Simone, Finite Mathematics, McGraw Hill, 1965.
  2. A.W. Goodman and J.S. Ratti, Finite Mathematics with Applications, 3rd edition, Macmillan, 1979.

��, 18 ���: ������� ��������� ��� ������� ��� ��������, ������ ���������� ��� ������� [n] = {1, 2, ..., n}, ��������� �������� k, ����������, �� ������� ��� Pascal, �� ��������� ������� ��� ���������

���������� �� 1� �������� ��������.

��, 23 ���: ������ ��������� ��������� ������� ������� ��� �� ���������� ������, ������ ������� �������� (��� �� ������, ���������� ��� �� ����� �� ���������� ������� �������, ������) ��� ������� �� ������� ���������� � ���������� ��� ������� ��������� ���������. ������� ���������� �� ���������: �� ������� �� ���������� ���� ��� ������� ������.

���� ��� ������� ��� �� ������ (�� �� ��������� ���) (i) ������� ��� (ii) ���� ����� ��� Internet (������ �������� ��� �� ��� ������ ������ ���������� �� ���������� ����� �������). ������������ ���� �� ������ ��� �� ��� �������� �� ��� ������ ������������ ��� ������������ Rutgers (�.�.�.) ���� �� ������ �������� �������� (��� ��� ������ ����!) ��������� �� ����� ��� �� ��� ������������ ���� �� �������. ������������ �� ��� ������ ���� (� ���� ��� ������ ��������). (23/2/98)

��, 25 ���: ������������� �� ��������� (����), �� ������ ������� ������ �� ������ �� k ��� �������� n �� ��������� ��������, ������������ ���������� (�� �������� a ~ b), � ����� ��� Stirling, �� ������� ��� ���������� ���������� C(n, k).

���������� �� 2� �������� ��������.

��, 27 ���: ����� ��� ��� �������� (9-10), ������ ���� ��� 2� �������� ��������.

�� ����� ���������� �� ����� ��� ����� ��� 2�� ���� ��� ������� 4 ������� �� �������� ���������� ��� ��� 20 ������� �����.

��, 4 ���: �������� ��� ���������: ����, �������������. ������� ��������������. ��������. ������ ���������. ������������ ��� ��������� ������������. ��������� ��� ���������. ������ ��������� ��� ��������� Euler ��� Hamilton. ������. ��������� ���������, ���������� ����������. �������� (��� ��������� ���������), ���������. ������ (= ��������� ��������� ����� �������).
����� �� ����� 15������ ����������.

��, 8 ���: �� ������������ ��� 1�� ������������� ����� ��������� ��� ��� �� ������� ���. �� ����� ����� ���� ���� (�) � ������� ����������� ��� ������� ���������� ��� (�) � �� �������� ��� ��� n! ��� �� �������� � ����� �� ��� ����� ������������� �� ������.

��, 9 ���: ������ �� n ������� ���� n-1 �����. ������ ��� �������� (spanning trees), �������� ������ ��� �������� �� ��������� �� ����. �������� ��� � �������� ���������� (greedy algorithm) ����� �������� ������.

��, 11 ���: ��������� ����������. ������� ��� �������� Euler. �������� ��� ����� ������� ��� ��� ������ ���������� Euler. ���������� �� ��������� �� ����. � ���������� Floyd-Warshall ��� ��� ������ ��� ���������� ������� �� ���� ������ �������. �������� ��� ��� ��������. � ���������� Dijkstra ��� ��� ������ ��� ���������� ��� ��� ������� ����� �� ����� ��� ����������. �������� ��� ��� ��������.

��, 16 ���: ����������� ������� ��� �����, ���������� ������� �(G) ���� ����������, ������� ������� ��� G. �� ��� ������ �(G) <= d+1, ���� d � �������� ������ ��� ����������. ��� ���� ������� ����� Ramsey (��� �� ���� ���������� ����� ��� K6 ������� ������ ������������� �������). ��������� ����� ������������ (���) ��� ����������� ���������� A1, A2, ..., An ��� ������� X. ��������� �������� ��� ���������� ��� ����� (������� Hall).
� � � � � � �:
��������� ��� ������� ��� �� ��������� ������ ���� ���������� �� ����� ����� �����. ���� ��� � �(G) ����� ��� ��������� ��� t+1, ���� t ����� � ����� ������ ��� ����������. ���� ����� �����! ������������ �� ������ ��� ������� �� �(G) �� ����� ��� �� 100 ��� �� t < 3.

����� ������� �� ����� ��� �������� ��� 28�� �������. � ��� ��� �� ��������� �� ����� �,�� ������ ������� ����� ��� ��� ����������� �������� ��� ����.

��� ������ �� Postscript ��� �� ������� ��� �����.

������� �� ����� ��� ������, 2 ��������, 8-10��, ��� ���� ���������� ��� ���� �������� �201 ��� �207.

��, 18 ���: ������������ � �������� ��� ���������� ��� Hall ��� ��������� ����� ������������. ��������� ����� ������������ ��� �������� ��������� �������. ���������, ������� ��� �� ���� �������� ������� ������� ������� ��� ��������� ��� ��������� ������� 1-1 �� ��� ������. ������ ������������ �� �� ��������� ������ ��� ���������� Cn (������ �� n �������).
����� �� ������� 15������ ����������.

��, 23 ���: ��� ����� ������ ���� ��������� ��� ����������.

��, 25 ���: �����.

������� ������: ���������, 27 �������, 6-8��, ���. ��. �� ������ ������ ��������.

����������: ��� ���� ������� �������� ��� ������ ���������� (Postscript).
��� ����� ��������� ��� �������� ��� ����������.

������� �� ����� ��� ������, 2 ��������, 8-10��, ��� ���� ���������� ��� ���� �������� �201 ��� �207.
� � � � � � � � � � � � � � � � � �.

��, 30 ���: �������� ��� ������� ���������. ���������� �� ������� ��� Euler (V+F = E+2) ��� ����� �� ������� ��� 5 �������� ("���� �������� ������ ������ �� ����������� �� 5 ������� ���� ����� ��� ����������� �� ����� ����������� �������").

���� ��������: �����, 31 �������, 8-10��, ��� ��.

��, 5 ���: �� ������ ��� ���� ������ ���������� ��� ���� ��� �� ���������� ���� ��� ������.

��, 6 ���., ��� ��, 8 ���.: ���������� ����������� ����������. ��� ���� ��� ��� ��������� ��� ��������� ��������� ��� ����������. ��� ���������������� �� ���������� ����������� ��� ��� ������ �������� ����� ��� ���������� ���� ������� �������� ����� ��� ��� ���������� ����������� ���� ��� �������� ��� ������� ������ �� ���������� ���������� ����������.
������ ������ ������� ���� ��������� �� ������� ������ ��� ������� ���� ��� ��������� ��������� ���� ���������� ���'������� ��� �� ����������� ��������� ��� ����������.

��� �������, 29 ��������, �� ����� �� ������� ���������� ���� ���� 5� ��� 6� ����� ��������.

��, 27 ���., ��� ��, 29 ���.: �������� ��� �������� ����������. � ����������� ����� � ��� � ���������� ���� ����������� (���������� ��� �). ������������. ���������� � 7� ����� ��������.

��, 3 �����: �� ������ ��� ��� �� 3� ���������� ���������� ���.


���� ��� ���� ��� �������.