%EASY
% This is EASY.TEX in text format, as of 87-06-11.
% EASY.TEX version 2.1 by H.Partl, TU Wien.
% This file consists of two parts:
% - the original (version 1) EASY.TEX definitions,
% - a subset of file GERMAN.TEX with additional definitions.
%
% EASY.TEX is a minimal macro package for TeX, using some
% ideas from The TeXbook by D.E.Knuth and LaTeX by L.Lamport.
% It also contains definitions for the easy use of the german
% language (with ideas by N.Schwarz & J.Krieger, Bochum, and
% T.Hofmann, Basel).
% In addition, there exist ``document style files'' ARTii.TEX
% and REPii.TEX, which can be used as supplements to EASY.TEX.
%
% It should be possible to call (\input) this macro file
% several times within one TeX input, e.g. at the beginning
% of each subfile, if the main file inputs several subfiles
% for parts of a longer document.
% If EASY.TEX has been called before (i.e. if \center is already
% defined), \input easy is terminated at once by \endinput without
% redefining anything.
% \ifundefined (which has been taken from The TeXbook) is used
% for this purpose.

\def\ifundefined#1{\expandafter\ifx\csname#1\endcsname\relax}
\ifundefined{center} % \then continue processing this file
\else \endinput \fi

\message{`EASY.TEX' Version 2.1 vom 11. Juni 1987.}

% AESTHETICS
%
% \sloppy     tolerate ugly line and page stretching
% \fussy      make it beautiful (TeX standard)
%             (These macros are taken from LaTeX)

\def\sloppy{\tolerance 2000 \hfuzz .5pt \vfuzz .5pt}
\def\fussy{\tolerance 200 \hfuzz .1pt \vfuzz .1pt}

% UMLAUTE
%
% The following is a redefinition of the \" control sequence
% that enables automatic hyphenation in the part of the word
% following the Umlaut. (In PLAIN.TEX, automatic hyphenation
% stops at the first occurrence of an Umlaut in any word.)
% This macro was found by N.Schwarz in Bochum.

\def\"#1{{\accent127 #1\penalty10000\hskip0pt plus0pt}}

% And here is the same for \ss (scharfes s):

\def\ss{{\char25\penalty10000\hskip0pt plus0pt}}

% CONTROL SEQUENCES
%
% "o        Umlaut-o (easier to use than \"o)
% \3        scharfes s (easier to use than \ss )
% \tie      ~ (for users of Hazeltine terminals,
%           where the tilde cannot be seen)
% \today    today's date in the form  d. m. yyyy
% \date     today's date in the form yyyy-m-d

\catcode`\"=\active  \let"=\"
\let\3=\ss
\let\tie=~
\def\today{\hbox{\number\day.~\number\month.~\number\year}}
\def\date{\hbox{\number\year-\number\month-\number\day}}

% Macros for german quotes (``Anfuehrungszeichen''):
%
% ,,xxx``   ,xxx`
%
% These macros, that involve some re-definitions and also disable(!)
% the special meaning of ?` and !`, have been designed by N.Schwarz
% at the Ruhr University of Bochum (Germany).
%
% You can use the command
% \nongermanquoting
% to remove these effects and to enable the spanish ?` and !`
% ligatures.

\def\komma{,}
\catcode`\,=\active
\catcode`\?=\active
\catcode`\!=\active
\def\ignore#1{}
\def?{\char63{\kern0pt}}
\def!{\char33{\kern0pt}}
\def,{\komma\futurelet\next\commatest}
\def\commatest{\ifmmode\else \ifx\next,\kern-.11em\fi \fi}

\def\nongermanquoting{\catcode`\,=12  \catcode`\<=12
    \catcode`\>=12  \catcode`\?=12  \catcode`\!=12  }

% DOCUMENT LAYOUT
%
% \Narrower       is the same as \narrower, except that
%                 \displayindent is used rather than
%                 \parindent: It indents paragraphs
%                 left and right.
% \singlespacing  resets \baselineskip to \normalbaselineskip
% \halfspacing    sets \baselineskip to 1.5 character heights
% \doublespacing  sets \baselineskip to 2.0 character heights
%                 Note: If you use non-zero parskip, you
%                 should make \parskip larger, too.
%                 Recommended values are
%                 \parskip=1.5\medskipamount  for halfspacing,
%                 \parskip=2\medskipamount    for doublespacing.

\def\Narrower{\advance\leftskip by \displayindent
             \advance\rightskip by \displayindent}
\def\singlespacing{\baselineskip=\normalbaselineskip}
\def\halfspacing{\baselineskip=1.3\normalbaselineskip}
\def\doublespacing{\baselineskip=1.6\normalbaselineskip}

% \condbreak{space}   conditional break
%                     If there is less than `space' vertical
%                     space left on the current page, then
%                     a new page is started, else do-nothing.
%                     (This is a weaker version of \filbreak.)

\def\condbreak#1{\vskip 0pt plus #1\penalty-500\vskip 0pt plus-#1}

% ENVIRONMENTS
%
% \center       the following lines until \endcenter
%               will be printed centered.
% \flushleft    the following lines until \endflushleft
%               will be printed flushed to the left.
% \flushright   the following lines until \endflushright
%               will be printed flushed to the right.
% \xxx and \endxxx must be properly paired, nesting is allowed.
% Notes: Input lines may be too long, then they will be split
% and each part will be centered or flushed, respectively.
% The macros do not say \obeyspaces, because you may need spaces
% to end command names. You can use the tie (tilde) or \quad or
% the like to produce "hard blanks" for indentation etc.
% If you don't like the \parskip before this environment,
% you should say  \vskip-\parskip  before saying \center etc.
%               (These macros use some ideas from LaTeX)

\def\center{\vskip\parskip\begingroup
            \parindent=0pt \parskip=0pt plus 1pt
            \rightskip=0pt plus 1fill \leftskip=0pt plus 1fill
            \obeylines}
\def\endcenter{\endgroup}
\def\flushleft{\vskip\parskip\begingroup
            \parindent=0pt \parskip=0pt plus 1pt
            \rightskip=0pt plus 1fill \leftskip=0pt
            \obeylines}
\def\endflushleft{\endgroup}
\def\flushright{\vskip\parskip\begingroup
            \parindent=0pt \parskip=0pt plus 1pt
            \rightskip=0pt \leftskip=0pt plus 1fill
            \obeylines}
\def\endflushright{\endgroup}

% LISTS (ITEMIZE)
%
% \itemize{width}
% \litem{label}text or \ritem{label}text
% \litem{label}text or \ritem{label}text
% ...
% \enditemize
%                   This is an extension to \item:
%                   The width of the indentation is specified
%                   in the call of \itemize, and the item label
%                   is printed left bound (by \litem) or right
%                   bound (by \ritem).
% \itemize and \enditemize must be properly paired, nesting
% with other environments (also between \litem- or \ritem-
% paragraphs) is allowed.

\def\itemize#1{\par\begingroup\parindent=#1}
\def\litem#1{\par\hang\noindent\hbox to \parindent{#1\hfil}}
\def\ritem#1{\par\hang\noindent\hbox to \parindent{\hfil#1\enspace}}
\def\enditemize{\par\endgroup\par}

% \bitem      This is a \ritem with a bullet as argument.

\def\bitem{\ritem{$\bullet$}}

% BOXES
%
% \disbox     the following (until \enddisbox) forms a box
%             similar to that for displayed equations, but to be
%             used for texts rather than mathematics.
%             It is indented by \displayindent (left and right),
%             and it is a box, i.e. page breaks are inhibited.
%             Inside the box, all lines, environments, tables etc.
%             work as on a mini-page with the shorter line length.
% \disbox and \enddisbox must be properly paired, nesting
% with other environments and within disboxes is allowed.

\def\disbox{\vskip\parskip \hbox to\hsize\bgroup
            \hskip\displayindent \vbox\bgroup
            \advance\hsize by-2\displayindent \line{}
            \prevdepth=0pt \vskip-\parskip }
\def\enddisbox{\egroup\hss\egroup}

% \example     The following lines (until \endexample)
%              are printed flushleft with \tt font in
%              a \disbox. This is primarily intended
%              for displaying short examples of source
%              programs or the like. In contrast to verbatim,
%              TeX commands (including font changes) can be
%              used with the text.
% \example and \endexample must be properly paired, nesting
% with other environments is allowed.

\def\example{\disbox \flushleft\tt}
\def\endexample{\endflushleft\enddisbox}

% \framebox and \endframebox
%           put a frame around the text between them. The frame
%           has the full line width, the lines inside the box
%           are shortened to leave free the frame. Like hrules,
%           there is no additional space above and below the box
%           (you must use \bigskip or the like to achieve this).
%           If you do not like the \parskip before the first
%           paragraph or environment inside the box, you should
%           say  \vskip-\parskip  just after \framebox.
% \framebox and \endframebox must be properly paired, and
% all sorts of nesting are allowed (e.g. a framebox inside a disbox,
% or \center inside a framebox, or a double framebox ... ).

\def\framebox{\hrule height.6pt \hbox to\hsize\bgroup
              \vrule width.6pt \hskip 9.5pt
              \vbox\bgroup
              \advance\hsize by-20.2pt \line{}
              \vskip 9.5pt \nointerlineskip}
%             note: 9.5 = medskip (6.0) + interlineskip (1.5+2.0)
%                       = the blank space between \par's.
%                   20.2 = 2 * 9.5 + 2 * .8
\def\endframebox{\vskip 9.5pt \egroup \hss \vrule width.6pt
                 \egroup \hrule height.6pt}

% VERBATIM
%
% \Obeylines      same as \obeylines, but empty lines are
%                 not ignored. (used internally by verbatim mode)
%
% \verbatim       The following(!) lines of input are printed
%                 verbatim (i.e. each character as it is, including
%                 blanks and TeX's special characters, without
%                 interpretion of TeX commands) until \endverbatim.
%                 This may be used to print examples of TeX input or
%                 source programs or any data.
% \verbatim and \endverbatim must be properly paired, and they may be
% called inside some other environment.
%                 (This macro is taken from appendix D of The TeXbook)

\def\uncatcodespecials{\def\do##1{\catcode`##1=12}\dospecials
    \do\@\do\"\do\?\do\!\do\,\do\<\do\>}          % modified (GR)
%                     note that " is active, too.
\def\setupverbatim{\tt\Obeylines\uncatcodespecials\obeyspaces}
\def\newlinepar{~\par}
{\catcode`\^^M=\active % these lines must end with `%'
  \gdef\Obeylines{\catcode`\^^M=\active\def^^M{\newlinepar}}}
{\obeyspaces\global\let =\ }
\def\verbatim{\par\begingroup\parskip=0pt plus 1pt
              \setupverbatim\doverbatim}
{\catcode`\|=0 \catcode`\\=12
 |Obeylines|gdef|doverbatim^^M#1\endverbatim{#1|endgroup}}

% \inputverbatim{filename}
%                 The file `filename.TEX' is `input' and
%                 listed in verbatim mode.
%                 This may be used to print entire TeX input files
%                 or source program files or data files.
%                 (This macro is taken from appendix D of The TeXbook)

\def\inputverbatim#1{\par\begingroup\parskip=0pt plus 1pt
                     \setupverbatim\input#1 \endgroup}

% \verb|text|     The first character after \verb is defined as
%                 the delimiter, then the following characters
%                 are printed verbatim until the second occurrence
%                 of the delimiter. This may be used to print a short
%                 sequence of TeX commands or special characters
%                 inside a normal text.
% Caution: \verb can NOT be used inside an argument to a macro!
%                 (This macro is taken from appendix D of The TeXbook)

\def\verb{\begingroup\setupverbatim\doverb}
\def\doverb#1{\def\next##1#1{##1\endgroup}\next}

% TABLES
%
% The following is one way to extend the features of \settabs.
% You don't get ready-made macros, but you will have to define
% your own macros for each table, as follows:
%          First, chose a name `nnn' for each column of the table,
%          and define the format, width `www' and font `\ff' for
%          each column:
% \def\nnn#1{\hbox to www{\ff #1\hfil}}
%          for a left bound single-line entry,
% \def\nnn#1{\hbox to www{\hfil \ff #1}}
%          for a right bound single-line entry,
% \def\nnn#1{\hbox to www{\hfil \ff #1\hfil}}
%          for a centered single-line entry,
% \def\nnn#1{\vtop{\hsize=www \parindent=0pt \sloppy \ff #1\par}}
%          for a (short) paragraph with automatic line splitting.
%          Then, define the table (don't forget to leave space
%          between the columns, using \quad or \hskip.5cm or the like,
%          and don't exceed the line length):
% \settabs\+\nnn{x}\quad&\nnn{x}\quad& ... &\nnn{x}\cr
%          where x may be any non-blank character.
%          Now, everything is set up, and you can generate table rows
%          by
% \+\nnn{text}&\nnn{text}& ... &\nnn{text}\cr
%          (but better start a new line of input after each &)
%          and you may put anything like \medskip and/or \hrule etc.
%          between the rows.
%
% Note: If you want the table to fill the line exactly to its margins,
% the sum of the box widths plus column separations must equal \hsize.
% This can be achieved by calculating the width for one of the boxes
% by
%    \newdimen\restwidth
%    \restwidth=\hsize
%    \advance\restwidth by -sss
% where sss is the sum of the lenghts of the other boxes plus all
% column separations, and then using \restwidth as the width of that
% box.

% This is the end of the 1st part of EASY.TEX.
% Now follows a subset of GERMAN.TEX:
%GERMAN
% This is GERMAN.TEX or GERMAN.DOC or GERMAN.STY, as of 87-06-09,
%    by H.Partl (TU Wien),
%    using ideas by W.Appelt, F.Hommes et al. (GMD St.Augustin),
%    T.Hofmann (CIBA-GEIGY Basel), and N.Schwarz (Uni Bochum).
% DOCUMENT STYLE OPTION for writing german texts with TeX or LaTeX.
% It can be called via
%    \input german
% or (with LaTeX) via
%    \documentstyle[german]{anystyle}
%
% General Commands and Features:
% \umlautlow        redefines the Umalut accent such that the dots come
%                   nearer to the letter and that hyphenation is enabled
%                   in the rest of the word.
% \umlauthigh       restores \" to its original meaning.
% \ss               is \lcc'ed to enable hyphenation.
% \mdqon            makes " an active (meta-) character that does the
%                   pretty things described below.
% \mdqoff           restores " to its original meaning.
% \adate, \ddate, \edate, \fdate  redefine \today to use the Austrian,
%                   german, english or french date format, resp.
% At the end, the settings appropriate for german texts are switched on.
%
% Detailled Commands to be used after \mdqon is switched on:
% "a                 for Umlaut-a  (like \"a), and also for other vowels
% "s  or \3          for sharp s   (like \ss{})
% "ck or \ck         for ck to be hyphenated as k-k
% "ff                for ff to be hyphenated as ff-f, and also for other
%                    consonants
% "|                 to separate ligatures
% "-                 like \-, but allowing hyphenation in the rest of the word
% ""                 like \-, but producing no hyphen sign
% "` or \glqq        for german left  double quotes  (similar to ,,)
% "' or \grqq        for german right double quotes  (similar to ``)
%       \glq         for german left  single quotes  (similar to , )
%       \grq         for german right single quotes  (similar to ` )
% "< or \flqq        for french left  double quotes  (similar to <<)
% "> or \frqq        for french right double quotes  (similar to >>)
%

{\catcode`\@=11 % \makeatletter

\gdef\allowhyphens{\nobreak\hskip 0pt plus 0pt\relax}

\newcount\U@C\newbox\U@B\newdimen\U@D
\gdef\umlauthigh{\def\"##1{{\accent127 ##1}}}
\gdef\umlautlow{\def\"{\newumlaut}}         % Plain TEX version only <---
% \gdef\umlautlow{\def\"{\protect\newumlaut}} % LATEX version only <---
\gdef\newumlaut#1{\leavevmode\allowhyphens
     \vbox{\baselineskip 0pt\lineskip.25ex
     \ialign{##\crcr\hidewidth
     \setbox\U@B=\hbox{#1}\U@D=.01pt\U@C=\U@D
     \U@D=\ht\U@B\advance\U@D by-1ex\divide\U@D by\U@C
     \U@C=\U@D\U@D=\the\fontdimen1\the\font
     \multiply\U@D by\U@C\divide\U@D by100\kern\U@D
     \vbox to .2ex{\hbox{\char127}\vss}\hidewidth\crcr#1\crcr}}%
     \allowhyphens}

\gdef\glqq{{\setbox0=\hbox{\lower1.36775ex%
          \hbox{''}\kern-.04em}\dp0=.36775ex\leavevmode\box0\allowhyphens}}
\gdef\grqq{\kern-.07em``\kern.07em}
\gdef\glq{{\setbox0=\hbox{\lower1.36775ex%
          \hbox{'}\kern-.04em}\dp0=.36775ex\leavevmode\box0\allowhyphens}}
\gdef\grq{\kern-.07em`\kern.07em}
\gdef\flqq{\ifmmode \ll \else \leavevmode
        \raise 0.2ex \hbox{$\scriptscriptstyle \ll $}\fi }
\gdef\frqq{\ifmmode \gg \else \leavevmode
        \raise 0.2ex \hbox{$\scriptscriptstyle \gg $}\fi }

\lccode`\^^Y=`\^^Y    % enable hyphenations after \ss
\gdef\ck{\allowhyphens\discretionary{k-}{k}{ck}\allowhyphens}
\global\let\3=\ss

\gdef\mdqon{\catcode`\"=\active}
\gdef\mdqoff{\catcode`\"=12\relax}

{\mdqoff
\gdef\@UMLAUT{\"}
\gdef\@MATHUMLAUT{\mathaccent"707F}
\gdef\@SS{\mathchar"7019}
\gdef\@QUOTE{"}
}

{\mdqon
\gdef"#1{\if\string#1`{\glqq}%
\else\if\string#1'{\grqq}%
\else\if\string#1a{\ifmmode\@MATHUMLAUT{a}\else\@UMLAUT{a}\fi}%
\else\if\string#1o{\ifmmode\@MATHUMLAUT{o}\else\@UMLAUT{o}\fi}%
\else\if\string#1u{\ifmmode\@MATHUMLAUT{u}\else\@UMLAUT{u}\fi}%
\else\if\string#1A{\ifmmode\@MATHUMLAUT{A}\else\@UMLAUT{A}\fi}%
\else\if\string#1O{\ifmmode\@MATHUMLAUT{O}\else\@UMLAUT{O}\fi}%
\else\if\string#1U{\ifmmode\@MATHUMLAUT{U}\else\@UMLAUT{U}\fi}%
\else\if\string#1s{\ifmmode\@SS\else{\ss}\fi}%
\else\if\string#1-{\allowhyphens\-\allowhyphens}%
\else\if\string#1\string"{\hskip 0pt plus 0pt\relax}%
\else\if\string#1|{\hyphenation{-}{}{\kern.03em}}%
\else\if\string#1c{\allowhyphens\discretionary{k-}{}{c}\allowhyphens}%
\else\if\string#1f{\allowhyphens\discretionary{ff-}{}{f}\allowhyphens}%
\else\if\string#1l{\allowhyphens\discretionary{ll-}{}{l}\allowhyphens}%
\else\if\string#1m{\allowhyphens\discretionary{mm-}{}{m}\allowhyphens}%
\else\if\string#1n{\allowhyphens\discretionary{nn-}{}{n}\allowhyphens}%
\else\if\string#1p{\allowhyphens\discretionary{pp-}{}{p}\allowhyphens}%
\else\if\string#1t{\allowhyphens\discretionary{tt-}{}{t}\allowhyphens}%
\else\if\string#1<{{\flqq}}%
\else\if\string#1>{{\frqq}}%
\else \@QUOTE #1%
\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi}
}


\gdef\adate{\def\today{\number\day.~\ifcase\month\or
  J\"anner\or Feber\or M\"arz\or April\or Mai\or Juni\or
  Juli\or August\or September\or Oktober\or November\or Dezember\fi
  \space\number\year}}
\gdef\ddate{\def\today{\number\day.~\ifcase\month\or
  Januar\or Februar\or M\"arz\or April\or Mai\or Juni\or
  Juli\or August\or September\or Oktober\or November\or Dezember\fi
  \space\number\year}}
\gdef\edate{\def\today{\ifcase\month\or
 January\or February\or March\or April\or May\or June\or
 July\or August\or September\or October\or November\or December\fi
 \space\number\day, \number\year}}
\gdef\fdate{\def\today{\number\day\space\ifcase\month\or
  janvier\or f\'evrier\or mars\or avril\or mai\or juin\or
  juillet\or ao\^ut\or septembre\or octobre\or novembre\or d\'ecembre\fi
  \space\number\year}}


} % return to previous catcodes

% Now, switch on what is appropriate for german:
\mdqon
% To provide compatibility, \umlautlow and \ddate are not called!

% This is the end of EASY.TEX (version 2).

%ART12
% This is ART12.TEX in text format, as of 1986-09-15.
% It is one of the document style files, version 1.0, by PA, TU Wien.
% (Change or delete these header lines, if you modify the file 
%  for your own purposes!)
% 
% Macros for ARTICLES with character size 12 POINTS, 
% to be \input at the beginning of your TeX file. 
  
% It should be possible to call (\input) this macro file 
% several times within one TeX input, e.g. at the beginning
% of each subfile, if the main file inputs several subfiles
% for parts of a longer document.
% If any of the document style files ARTii.TEX, REPii.TEX has 
% been called before (i.e. if \chapter is already defined),
% the \input of this file is terminated at once by \endinput without 
% redefining anything.
% \ifundefined (which has been taken from The TeXbook) is used 
% for this purpose. 
  
\def\ifundefined#1{\expandafter\ifx\csname#1\endcsname\relax} 
\ifundefined{chapter} % \then continue processing this file 
\else \endinput \fi 
  
\magnification=\magstep1 % everything is multiplied by 1.2! 
  
% FONTS 
% 
% The following font names are defined:
% \large     14.4 point roman
% \largebf   14.4 point bold face 
% \Large     16.8 point roman 
% \Largebf   16.8 point bold face
% \small     10.8 point roman
% \smallit   10.8 point text italic 
  
\font\large=cmr10 scaled \magstep1 
\font\Large=cmr10 scaled \magstep2
\font\largebf=cmbx10 scaled \magstep1 
\font\Largebf=cmbx10 scaled \magstep2
\font\small=cmr9 % must be loaded explicitly
\font\smallit=cmti9 % must be loaded explicitly
  
% The following skips may be used like \bigskip etc. 
% They contain much stretchability, so that TeX has good chances 
% to break pages where you have said \goodbreak by stretching the 
% space between (not inside) chapters, sections etc.
  
\def\articleskip{\vfill\eject}
\def\chapterskip{\vskip 1.5cm plus .75cm minus .5cm}
\def\sectionskip{\vskip 24pt plus 12pt minus 8pt} 
\def\subsectionskip{\vskip 12pt plus 12pt minus 4pt} 
\def\subsubsectionskip{\vskip 9pt plus 9pt minus 3pt} 
  
% super-goodbreaks (stronger than \goodbreak, which gives 
% a penalty of -500, for chapter and section breaks). 
  
\def\Goodbreak{\par\penalty-750 }
\def\GOODbreak{\par\penalty-1000 }
  
% SECTION HEADINGS
% 
% \chapter \section \subsection \subsubsection 
%      write their argument as header to the chapter, section... 
%      If you want to start a section, subsection... without any 
%      head line, then you do not need to call \section... 
%      The text of the heading may be longer than one line, TeX will 
%      split it for you, or you may say \par to split it at a certain 
%      point.
  
% SPACING BETWEEN SECTIONS
% 
% \endchapter \endsection \endsubsection \endsubsubsection 
%     produce the (stretchable) space that is to occur between
%     two consecutive chapters, sections... 
% \chapter... and \endchapter... need NOT be paired exactly. 
%     You will not put \endsection after the last section of a
%     chapter just before \endchapter, and you will put 
%     \endsection before the first \section header, if there
%     has been some general text (plain paragraphs) before the
%     first section header in a chapter.
  
\outer\long\def\chapter#1{{\parindent=0pt 
    \parskip=0pt \advance\baselineskip by\smallskipamount \leftskip=0pt
    \rightskip=10pt plus 1fil minus 10pt \par\largebf#1\par} 
    \nobreak\subsectionskip\nobreak} 
\outer\def\endchapter{\par\GOODbreak\chapterskip\GOODbreak} 
\outer\long\def\section#1{{\parindent=0pt 
    \parskip=0pt \advance\baselineskip by\smallskipamount \leftskip=0pt
    \rightskip=10pt plus 1fil minus 10pt \par\bf#1\par} 
    \nobreak\subsubsectionskip\nobreak} 
\outer\def\endsection{\par\Goodbreak\sectionskip\Goodbreak} 
\outer\long\def\subsection#1{{\parindent=0pt 
    \parskip=0pt \leftskip=0pt 
    \rightskip=10pt plus 1fil minus 10pt \par\rm#1\par} 
    \nobreak\medskip\nobreak} 
\outer\def\endsubsection{\par\goodbreak\subsectionskip\goodbreak} 
\outer\long\def\subsubsection#1{{\parindent=0pt 
    \parskip=0pt \leftskip=0pt 
    \rightskip=10pt plus 1fil minus 10pt \par\it#1\par} 
    \nobreak\smallskip\nobreak} 
\outer\def\endsubsubsection{\par\goodbreak\subsubsectionskip\goodbreak} 
  
% \article{title of the article}
%     may be used to print a title to your article, but you may 
%     prefer to print other things there or to use other formats. 
%     Note that you may use 
%     \article{first line of title\par second line of title} 
% 
% \endarticle 
%     may be used to end your article or to skip to another article, 
%     but you are not forced to do so.
  
\outer\long\def\article#1{\par{\parindent=0pt
    \parskip=0pt \advance\baselineskip by\smallskipamount
            \rightskip=0pt plus 1fill \leftskip=0pt plus 1fill 
            \Largebf #1 \par} 
            \nobreak\sectionskip\nobreak} 
\outer\def\endarticle{\par\GOODbreak\articleskip\GOODbreak} 
  
% LAYOUT
% 
% The following commands set up the layout of the document
% (paragraph shapes, aesthetics etc.) 
% They CHANGE some of the definitions and settings of PLAIN.TEX,
% so that your document will look different, and various of the 
% TeX commands will behave differently! 
  
\parindent=0pt   % no indentation of first line of paragraph. 
%                  Note that this affects also some macros
%                  like \item, \narrower etc. EASY.TEX contains
%                  macros that may be substitutes in this case. 
\parskip=\medskipamount   % non-zero spacing between paragraphs. 
%                           You may use 
%                           \vskip-\parskip 
%                           to remove this extra skip before a
%                           particular paragraph (e.g. before
%                           the first one in a box). 
\displayindent=1cm   % indentation for displays, \disbox, \Narrower...
\overfullrule=0pt   % do not mark overfull boxes
\hoffset=0.08truein % compensate for bad page positioning 
  
% The following are re-definitions of \makeheadline and \makefootline 
% that raise the head line and lower the foot line. This will look
% better on DIN-A4 paper.
\def\makeheadline{\vbox to 0pt{\vskip-.5truein
     \line{\vbox to8.5pt{}\the\headline}\vss}\nointerlineskip} 
\def\makefootline{\baselineskip=.5truein \line{\the\footline}}
  
% The following macros may be called to change the page layout: 
% \noheadlines     disables head lines and moves up the beginning 
%                  of the normal text per page by .5 inch.
% \nofootlines     disables foot lines and page numbers, and moves
%                  down the end of the normal text per page by .5 inch. 
% These macros should be called only once and only at the very beginning 
% of the document. 
\def\noheadlines{\def\makeheadline{}
                 \advance\voffset by-.5truein \advance\vsize by.5truein} 
\def\nofootlines{\def\makefootline{}\advance\vsize by.5truein} 
  
% \Footnote   a better version of \footnote, 
%             with internal and constant settings
%             of parindent, parskip and font.
  
\def\Footnote#1#2{{\parindent=1cm \baselineskip=11pt 
    \footnote{#1}{\vrule height10.5pt width0pt \small #2}}}
  
% This is the end of ART12.TEX.


\vsize = 21 cm
\hsize = 14.5 cm

\article{Kerne und Grundyfunktionen  auf B\"aumen}

\centerline{Michael Drmota}
\centerline{Technische Universit\"at Wien}

Sei $G=(E(G),V(G))$ ein einfacher gerichteter Graph mit Knotenmenge
$E(G)$ und Kantenmenge $V(G)$. Zu einer nichtleeren
Teilmenge $M \subseteq V(G)$ der Knoten bezeichne $\Gamma^+(M)$
die Menge der Nachfolgerknoten, $\Gamma^-(M)$ die Menge der
Vorg\"angerknoten und $\Gamma(M)=\Gamma^+(M)\cup \Gamma^-(M)$.
Eine Teilmenge $I\subseteq V(G)$ der Knotenmenge hei{\ss}t unabh\"angig
(oder innenstabil), falls $\Gamma(M) \cap M = \emptyset$ gilt,
d.h. zwei Knoten aus $I$ sind nicht adjazent. Eine Teilmenge
$D\subseteq V(G)$ der Knotenmenge hei{\ss}t von au{\ss}en stabil,
fall $\Gamma^-(M)\cup D = V(G)$ erf\"ullt ist, mit anderen Worten,
jeder Knoten, der nicht in $D$ liegt, ist Vorg\"anger eines Knoten
aus $D$. Ein Kern $K\subseteq V(G)$ eines Graphen ist dann eine
unabh\"angige und von au{\ss}en stabile Teilmenge der Knotenmenge. 
Graphen, die einer Kern besitzen, k\"onnen mit Hilfe einer 
Grundyfunktion (vgl. [{\bf Be}]) noch feiner untersucht werden.
Eine Grundyfunktion $g:V(G)\to \hbox{\bf N} = \{0,1,2,\ldots\}$
ist auf der Knotenmenge definiert und erf\"ullt f\"ur alle Knoten
$v \in V(G)$
$$
g(v) = \min (\hbox{\bf N} \setminus g(\Gamma^+(\{v\}))).
\eqno \hbox{(1)}
$$
Kerne sind dann genau die Urbilder $g^{-1}(\{0\})$.

Nun m\"ussen Kerne und Grundyfunktionen nicht immer existieren
bzw. nicht eindeutig sein. Man kann allerdings zeigen ([{\bf To}]),
da{\ss} fast alle gerichtete Graphen einen Kern und damit eine
Grundyfunktione besitzen. Besonders einfach ist die Situation jedoch
in zyklenfreien Graphen, wo eine eindeutig bestimmte Grundyfunktion
existiert. 

In dieser Note soll das Verteilungsverhalten von Kernen und 
Grundyfunktionen in ebenen Wurzelb\"aumen beschrieben werden, wo
alle Kanten von der Wurzel weg gerichtet sind. Und zwar sollen
einfach erzeugte Baumfamilien {\bf F} betrachtet werden.
Sei $\varphi(t) = 1+\varphi_1 t + \varphi_2 t^2 + \cdots$ eine
formale Potenzreihe mit nichtnegativen Koeffizienten $\varphi_i$.
Einem ebenen Wurzelbaum $T$ wird dann ein Gewicht $(\varphi_0=1)$
$$
\omega(T) = \prod_{i\ge 0} \varphi_i^{D_i(T)},
\eqno \hbox{(2)}
$$
wobei $D_i(T)$ die Anzahl der Knoten von $T$ mit Weggrad $i$ bezeichnet,
zugeordnet. Die erzeugende Funktion $Y(x) = \sum_{n\ge 1} y_n x^n$
der Zahlen $y_n = \sum_{|V(T)|=n} \omega(T)$ erf\"ullt dann die
Funktionalgleichung $Y = x\varphi(Y)$. In {\bf F} werden nun jene
ebenen Wurzelb\"aume $T$ mit $\omega(T) > 0$ aufgenommen. 
Ist $\varphi_i \in \{0,1\}$, so ist auch $\omega(T)\in \{0,1\}$ und
$y_n$ ist die Anzahl der B\"aume aus {\bf F} der Gr\"o{\ss}e $n$.
Beispielsweise werden durch $\varphi(t) = 1+t^2$ die Menge der
ebenen Bin\"arb\"aume und durch $\varphi(t) = 1+t+t^2+\cdots = 1/(1-t)$
alle ebenen Wurzelb\"aume beschrieben. 

Jeder ebene Wurzelbaum $T$, bei dem alle Kanten von der Wurzel $w$
weg gerichtet sind, besitzt eine eindeutig bestimmte Grundyfunktion $g$.
Sei $d_{m,i}(T) = 1$ $(m = (m_0,m_1,\ldots),$ $i \ge 0)$, falls
$g(w) = i$ gilt und f\"ur alle $j\ge 0$ die Anzahl der Knoten
$v \in V(T)$ mit $g(v) = j$ gleich $m_j$ ist. Andernfalls sei
$d_{m,i}(T) = 0$. Die erzeugenden Funktionen 
$D_i(x,y) = \sum_{m,n} d_{mn,i} y^m z^n$ $(y = (y_0,y_1,\ldots),$ 
$y^m = y_0^{m_0}y_1^{m_1}\cdots )$ der Gr\"o{\ss}en 
$d_{mn,i} = \sum_{|V(T)|=n} \omega(T) d_{m,i}(T)$ und
$D(x,y) = \sum_{i\ge 0} D_i(x,y)$ erf\"ullen dann die formalen
Funktionalgleichugen

{\bf Lemma 1.}
$$
\sum_{i\ge 0} {1 \over y_i} D_i(x,y) = x\varphi(D(x,y))
\eqno (3)
$$
$$
D_i(x,y) = xy_i \sum_{J\subseteq \{0,\ldots,i-1\}} (-1)^{|J|}
\varphi\biggl( D(x,y)-D_i(x,y) - \sum_{j\in J} D_j(x,y) \biggr),\quad i\ge 0.
\eqno (4)
$$

Es erscheint unm\"oglich, aus diesem i.a. unendlichen 
Funktionalgleichungssystem explizite Resultate zu erhalten. Es 
gelingt jedoch, mit analytischen Methoden asymptotische Aussagen
\"uber das Verteilungsverhalten der Werte der Grundyfunktionen
zu gewinnen. Die Gr\"o{\ss}en $d_{mn} = \sum_{i\ge 0} d_{mn,i}$ erf\"ullen
einen zentralen Grenzwertsatz mit relativ einfach zu bestimmenden
Mittelwerten
$$
\delta_n^{(i)} = {1 \over y_n} \sum_m m_i d_{mn}.
\eqno (5)
$$

{\bf Satz 1.} {\it Es sei der Konvergenzradius $R$ der 
Potenzreihe $\varphi(t)$
so gro{\ss}, da{\ss} die Gleichung $x\varphi'(x) = \varphi(x)$ eine 
L\"osung $0 < \tau < R$ besitzt. Damit besitzt auch das i.a.
unendliche System
$$
d_i = {\tau\over \varphi(\tau)} 
\sum_{J\subseteq \{0,\ldots,i-1\}} (-1)^{|J|}
\varphi\left( \tau -d_i - \sum_{j\in J} d_j \right),\quad i\ge 0.
\eqno (6)
$$
eindeutig bestimmte nichtnegative L\"osungen $d_i$ mit
$\sum_{i\ge 0} d_i = \tau$, und die Mittelwerte $\delta_n^{(i)}$ sind 
dann f\"ur jedes $i\ge 0$ asymptotisch durch
$$
\delta_n^{(i)} = {d_i\over \tau} n + O(1)
\eqno (7)
$$
gegeben.}

Etwas einfacher wird die Situation, wenn es ein $i_0$ gibt, soda{\ss}
f\"ur alle $i\ge i_0$ $\varphi_i = 0$ ist. F\"ur jeden Baum $T$ aus
{\bf F} ist dann die Grundyfunktion $g$ strikt durch $i_0$
beschr\"ankt. Demnach ist $d_i = 0$ f\"ur $i \ge i_0$  und das i.a.
unendliche System (6) reduziert sich auf ein endliches.

Betrachte man etwa die Familie der Bin\"arb\"aume mit 
$\varphi(t) = 1 + t^2$, so bestimmt man ohne Schwieriegkeiten
$\tau = 1$, $d_0 = 2-\sqrt 2 = 0.585\ldots$, $d_1 = (2\sqrt 2 -1)/7
= 0.261\ldots$ und $d_2 = (5\sqrt 2 -6)/7 = 0.153\ldots$. 
Daraus ermittelt man den mittleren Wert der Grundyfunktion
zu $0d_0 + 1d_1+2d_2 = (12\sqrt 2 - 13)/7 = 0.567\ldots$.

Es f\"allt auf, da{\ss} in diesem Beispiel $d_0/\tau > 1/2$ gilt,
was \"ubrigens ein Spezialfall der folgenden allgemeinen Eigenschaft ist.

{\bf Lemma 2.} {\it F\"ur $i \ge 0$ gilt
$$
d_i > \sum_{j>i} d_j.
\eqno (8)
$$
}

Da Kerne gerade jene Teilmengen der Knotenmengen sind, wo die
Grundyfunktion den Wert 0 annimmt, ist $(d_0/\tau)n > n/2$ etwa
die mittlere Gr\"o{\ss}e eines Kernes. Kerne besitzen aber sonst
keine innere Struktur, da wegen der Unabh\"angigkeit der von einem
Kern induzierte Teilgraph keine Kanten besitzt, also vollkommen
unzusammenh\"angend ist. Um jedoch einem besseren \"Uberblick 
bekommen zu k\"onnen, empfiehlt es sich Komplemente von Kernen 
$V(T)\setminus K$ zu betrachten. Die induzierten Teilgraphen der Komplemente
besitzen die Struktur eines Waldes, wo die Komponenten nicht unbedingt
nur aus einem Knoten bestehen m\"ussen. 
\"Uber diese Kompoenten  l\"a{\ss}t sich folgendes aussagen.

{\bf Satz 2.} {\it Sei} {\bf F} {\it eine einfach erzeugte Familie
von B\"aumen, wo alle Kanten von der Wurzel weggerichtet sind. Weiters
sei der Konvergenzradius $R$ von $\varphi(t)$ so gro{\ss}, da{\ss} die
Gleichungen $x\varphi'(x) = \varphi(x)$ und
$x(\varphi'(d_0+x)-\varphi'(d_0)) = \varphi(d_0+x)-\varphi(d_0)$
positive L\"osungen $0< \tau,\vartheta < R$ besitzen. ($d_0$ sei wie
oben definiert.) Dann ist die mittlere Anzahl $g_n^{(j)}$
der Komponenten der Gr\"o{\ss}e $j$ (der Komplemente der Kerne) in B\"aumen 
der Gr\"o{\ss}e $n$ asymptotisch durch
$$
g_n^{(j)} = \mu_j n + O(1)
\eqno (9)
$$
gegeben, wobei
$$
\mu_j = {\varphi'(\tau-d_0)\over \varphi(\tau)} \left( {\tau\over
\varphi(\tau)} \right)^j {1\over j} [t^{j-1}]
(\varphi(d_0+t)-\varphi(t))^j
\eqno (10)
$$
ist. Die mittlere Anzahl der Komponenten ist
$$
{\tau - d_0 \over \varphi(\tau)} \varphi'(\tau-d_0) + O({1\over n})
\eqno (11)
$$
und die mittlere Gr\"o{\ss}e einer Komponente
$$
{\varphi(\tau) \over \tau\varphi'(\tau-d_0)} +  O({1\over n}).
\eqno (12)
$$
Hingegen ist die mittlere Gr\"o{\ss}e der gr\"o{\ss}ten Komponente in B\"aumen
mit $n$ Knoten
$$
{ \log n \over \log {\varphi'(\tau)\over \varphi'(d_0+\vartheta)-
\varphi'(d_0)}} + O(\log\log n).
\eqno (13)
$$
}

Die f\"ur den Beweis notwendigen Methoden werden in [{\bf BD1}]
bereitgestellt, wo auch explizite Resultate gewonnen werden k\"onnen.
Verwandte Resultate findet man auch in [{\bf BD2}].

\section{Literatur}

{\small

[{\bf Be}]  C. Berge, {\it Graphes and Hypergraphes}, Dunod, Paris, 1970.

[{\bf To}] J. Tomescu, {\it Almost all Digraphs Have a Kernel},
Discr. Math. {\bf 84} (1990), 181--192. 

[{\bf BD1}] G. Baron and M. Drmota, {\it Distribution Properties of 
Induced Subgraphs of Trees}, Ars Combinatoria, zur Publikation eingereicht.

[{\bf BD1}] G. Baron und M. Drmota, {\it Die Komponentenverteilung 
von ges\"attigten Teilgraphen in Baumfamlien}, S\'eminaire Lotharingien 
de Combinatoire, 25$^e$ session, zur Publikation eingereicht. 

Michael Drmota, Abteilung f\"ur Diskrete Mathematik, Technische
Universit\"at Wien, Wiedner Hauptstra{\ss}e 8--10/118,
A-1040 Wien, \"Osterreich.
}
\end
