Netz (Diskrete Mathematik)

Ein Netz ist in der Diskreten Mathematik und der Geometrie die Bezeichnung für eine endliche Inzidenzstruktur mit einigen zusätzlichen Eigenschaften. Der Begriff verallgemeinert den Begriff affine Ebene und spezialisiert den Begriff affiner Blockplan. In einem Netz lässt sich wie in einer affinen Ebene eine Parallelitätsrelation allein aufgrund der Inzidenz definieren.

Definitionen und Eigenschaften

Eine endliche Inzidenzstruktur, also ein Tripel ${\displaystyle {\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)}$ von Mengen mit ${\displaystyle {\mathfrak {p}}\cap {\mathfrak {G}}=\emptyset }$ und ${\displaystyle I\subseteq {\mathfrak {p}}\times {\mathfrak {G}}}$ heißt Netz, wenn die folgenden Axiome erfüllt sind:[1]

1. Durch je zwei verschiedene Punkte ${\displaystyle p_{1},p_{2}\in {\mathfrak {p}}}$ geht höchstens eine Gerade ${\displaystyle G\in {\mathfrak {G}}}$.
2. Ist ${\displaystyle p\in {\mathfrak {p}},G\in {\mathfrak {G}}}$, und inzidiert p nicht mit G, dann existiert genau eine Gerade ${\displaystyle H\in {\mathfrak {G}}}$, die mit p inzidiert, aber mit keinem Punkt auf G inzidiert.
3. Jede Gerade inzidiert mit mindestens zwei Punkten. Es gibt einen Punkt, durch den mindestens zwei Geraden gehen. Gehen durch jeden Punkt genau zwei Geraden, so trägt jede Gerade gleich viele Punkte.[2]

Parallelitätsrelation

Durch das zweite Axiom ist es möglich, auf der Geradenmenge von ${\displaystyle {\mathcal {N}}}$ eine Parallelitätsrelation durch die Definition

${\displaystyle G\parallel H\quad \Leftrightarrow \quad \left(G=H\lor (G)\cap (H)=\emptyset \right)}$[3] einzuführen.

Kennzahlen eines Netzes

• Zu jedem Netz existieren natürliche Zahlen ${\displaystyle r,n\in \mathbb {N} }$ derart, dass durch jeden Punkt genau r Geraden gehen und auf jeder Geraden genau n Punkte liegen. In dieser Situation nennt man ${\displaystyle {\mathcal {N}}}$ ein ${\displaystyle (r,n)}$-Netz
• Es gilt stets ${\displaystyle r\leq n+1}$.
• Ist ${\displaystyle {\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)}$ ein Netz, so erhält man wieder ein Netz ${\displaystyle {\mathcal {N'}}=({\mathfrak {p}},{\mathfrak {G}}',I')}$, indem man aus der ursprünglichen Geradenmenge eine gewisse Menge von Parallelenscharen entfernt, dabei müssen dann nur wenigstens zwei Parallelenscharen übrig bleiben.
• Jede affine Ebene der Ordnung q ist ein ${\displaystyle (q+1,q)}$- Netz. Eine endliche Inzidenzstruktur ist genau dann eine affine Ebene, wenn sie ein ${\displaystyle (n+1,n)}$-Netz ist.
• Jedes ${\displaystyle (r,n)}$-Netz ist eine Inzidenzstruktur vom Typ ${\displaystyle (m,1),m\in \{1,2\}}$, also eine taktische Konfiguration. Genau dann, wenn ${\displaystyle m=2}$ ist, ist das Netz eine affine Ebene.

Beispiele und Gegenbeispiele

• Für eine beliebige natürliche Zahl ${\displaystyle n\geq 2}$ ist das endliche, ebene Gitter der Punkte ${\displaystyle {\mathfrak {p}}=\{(x,y)\in \mathbb {Z} ^{2}|\;1\leq x,y\leq n\}}$ mit den Parallelen zur x- und y-Achse als Geraden ein ${\displaystyle (2,n)}$-Netz. Ist n eine Primzahlpotenz, so kann man sich dieses Netz erzeugt denken aus einer affinen Ebene der Ordnung n, aus der alle Parallelenscharen außer den Parallelen zu den Koordinatenachsen, also ${\displaystyle n-1}$ Scharen, fortgelassen wurden.
• Das analog konstruierte endliche, räumliche Gitter hat 3 Geraden durch jeden Punkt und n Punkte auf jeder Geraden. Es ist eine Inzidenzstruktur vom Typ ${\displaystyle (1,1)}$, aber kein Netz, da das zweite Axiom (Eindeutigkeit der Parallelen) nicht erfüllt ist.
• Eine andere Verallgemeinerung des Begriffes affine Geometrie für beliebigdimensionale Räume ist der Begriff schwach affiner Raum. Erfüllt ein endlicher schwach affiner Raum das Axiom (A2e) „Es gibt eine natürliche Zahl ${\displaystyle s\geq 2}$, so dass jede Gerade g genau s Punkte enthält.“, und ist dieser Raum darüber hinaus im folgenden Sinne eben: „Sind zwei Geraden disjunkt, dann sind sie parallel.“, dann ist er ein Netz.
• Eine projektive Ebene ist nie ein Netz, da das zweite Axiom (Existenz der Parallelen) nicht erfüllt ist.

Konstruktion

Konstruktion aus lateinischen Quadraten

Aus jeder Liste von ${\displaystyle q}$ paarweise orthogonalen lateinischen Quadraten (MOLS = mutually orthogonal Latin squares) der Ordnung ${\displaystyle n}$ kann man ein ${\displaystyle (q+2,n)}$-Netz erzeugen.[4] Jedes der lateinischen Quadrate bestimmt die Inzidenzrelation für die ${\displaystyle n^{2}\,}$ Punkte ${\displaystyle {\mathfrak {p}}=\{(x,y)|x,y\in \{1,2,3,\ldots n\}\}}$ in Bezug auf eine Parallelenschar. Hinzu kommen die zwei Scharen, die parallel zur ${\displaystyle x}$- bzw. ${\displaystyle y}$-Achse sind. Details der Konstruktion sind im Artikel „Lateinisches Quadrat“ im Abschnitt Lateinisches Quadrat#Geometrie: Orthogonale lateinische Quadrate und endliche Ebenen beschrieben.

Das oben beschriebene Beispiel eines „Gitters“ mit zwei Parallelenscharen gehört auch zu diesem Typ. Es gehört zu einer leeren Liste von MOLS.

Umgekehrt bestimmen die ${\displaystyle r}$ Parallelenscharen eines ${\displaystyle (r,n)}$-Netzes eine Liste von ${\displaystyle r-2\,}$ MOLS der Ordnung ${\displaystyle n}$. Daher gilt: Ein ${\displaystyle (r,n)}$-Netz existiert genau dann, wenn ${\displaystyle r-2\leq R(n)}$ ist. ${\displaystyle R(n)}$, die Folge der größtmöglichen Anzahlen von paarweise orthogonalen lateinischen Quadraten der Ordnung ${\displaystyle n}$, ist Folge A001438 in OEIS.

Konstruktion aus kleineren Netzen

Aus einem ${\displaystyle (r,m)}$- und einem ${\displaystyle (r,n)}$-Netz lässt sich stets ein ${\displaystyle (r,m\cdot n)}$-Netz konstruieren.[4] Eine mögliche Methode ist in Lateinisches Quadrat#Orthogonale lateinische Quadrate und MOLS skizziert.

Anwendung: Authentifikation

Eine digitale Signatur ist ein Authentifikationssystem, mit dem gewährleistet werden soll, dass eine bestimmte Nachricht tatsächlich von einem bestimmten Sender kommt. Mit einem (r,n)-Netz ${\displaystyle {\mathcal {N}}}$ lässt sich eine solche digitale Signatur realisieren:[5]

• Die möglichen Datensätze sind die r Parallelenscharen des Netzes ${\displaystyle {\mathcal {N}}}$,
• die möglichen Schlüssel sind die ${\displaystyle n^{2}}$ Punkte des Netzes
• und die gesendeten Nachrichten sind Geraden von ${\displaystyle {\mathcal {N}}}$, eine Gerade (Nachricht) ist gültig, hat also die richtige digitale Signatur, wenn sie mit dem vereinbarten Punkt (dem Schlüssel) inzidiert.

Eine Verschlüsselung findet hier nicht statt: Aus der gesendeten Information, einer Geraden des Netzes, kann ein Angreifer selbstverständlich auf die Parallelenschar, also den Datensatz schließen, aber er kann nicht den Schlüssel erkennen. Ein Authentifikationssystem mit k Schlüsseln, bei dem ein Angreifer, der höchstens eine Nachricht kennt, nur mit einer Wahrscheinlichkeit von ${\displaystyle 1/{\sqrt {k}}}$ betrügen, das heißt eine eigene Nachricht als gültig senden oder eine authentische Nachricht durch eine andere ersetzen kann, nennt man perfekt, weil diese Betrugswahrscheinlichkeit gerade der Wahrscheinlichkeit für erfolgreiches „Raten“ eines Schlüssels ohne Vorinformation entspricht.

Das auf einem Netz beruhende Authentifikationssystem ist perfekt und man kann zeigen,[6][7] dass jedes perfekte Authentifikationssystem von einem Netz bestimmt wird. Die größtmögliche Anzahl an möglichen Datensätzen erhält man für ${\displaystyle r=n+1}$, also dann, wenn das Netz eine affine Ebene ist.

Literatur

• Albrecht Beutelspacher: Einführung in die endliche Geometrie. I. Blockpläne. B.I. Wissenschaftsverlag, Mannheim/Wien/Zürich 1982, ISBN 3-411-01632-9, Kapitel 3. Konstruktion von Blockplänen. 
• Albrecht Beutelspacher, Ute Rosenbaum: Projektive Geometrie. Von den Grundlagen bis zu den Anwendungen (= Vieweg Studium: Aufbaukurs Mathematik). 2., durchgesehene und erweiterte Auflage. Vieweg, Wiesbaden 2004, ISBN 3-528-17241-X (Inhaltsverzeichnis [abgerufen am 1. April 2012]). 
• Harris F. MacNeish: Euler squares. In: The Annals of Mathematics. Band 23, Nr. 3, März 1922, S. 221–227, JSTOR:1967920. 

Einzelnachweise und Anmerkungen

1. Beutelspacher (1982), Abschnitt 3.4 Rekursive Methoden
2. Die letzte Forderung wird nur in dem genannten Spezialfall erhoben, weil sie immer dann, wenn nicht durch jeden Punkt genau zwei Geraden gehen, aus den übrigen Axiomen bewiesen werden kann, Beutelspacher (1982), S. 131
3. Das Symbol ${\displaystyle (G)}$ steht für die Menge der mit der Geraden G inzidierenden Punkte, vgl. Inzidenzstruktur#Notation und grundlegende Begriffe.
4. MacNeish (1922)
5. Beutelsbacher und Rosenbaum, 6.3 Authentifikation
6. Beutelsbacher und Rosenbaum, Satz 6.3.4
7. Marijke De Soete, Klaus Vedder, Michael Walker: Cartesian Authentication Schemes. In: Advances in Cryptology — EUROCRYPT ’89. Band 434, 1990, S. 476–490, doi:10.1007/3-540-46885-4_46.