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 ${\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)$ von Mengen mit ${\mathfrak {p}}\cap {\mathfrak {G}}=\emptyset$ und $I\subseteq {\mathfrak {p}}\times {\mathfrak {G}}$ heißt Netz, wenn die folgenden Axiome erfüllt sind:

1. Durch je zwei verschiedene Punkte $p_{1},p_{2}\in {\mathfrak {p}}$ geht höchstens eine Gerade $G\in {\mathfrak {G}}$.
2. Ist $p\in {\mathfrak {p}},G\in {\mathfrak {G}}$, und inzidiert p nicht mit G, dann existiert genau eine Gerade $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.

Parallelitätsrelation

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

$G\parallel H\quad \Leftrightarrow \quad \left(G=H\lor (G)\cap (H)=\emptyset \right)$ einzuführen.

Kennzahlen eines Netzes

• Zu jedem Netz existieren natürliche Zahlen $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 ${\mathcal {N}}$ ein $(r,n)$-Netz
• Es gilt stets $r\leq n+1$.
• Ist ${\mathcal {N}}=({\mathfrak {p}},{\mathfrak {G}},I)$ ein Netz, so erhält man wieder ein Netz ${\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 $(q+1,q)$- Netz. Eine endliche Inzidenzstruktur ist genau dann eine affine Ebene, wenn sie ein $(n+1,n)$-Netz ist.
• Jedes $(r,n)$-Netz ist eine Inzidenzstruktur vom Typ $(m,1),m\in \{1,2\}$, also eine taktische Konfiguration. Genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=2} ist, ist das Netz eine affine Ebene.

Beispiele und Gegenbeispiele

• Für eine beliebige natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n\geq 2} ist das endliche, ebene Gitter der Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathfrak{p}=\{(x,y)\in \Z^2|\; 1\leq x,y\leq n\}} mit den Parallelen zur x- und y-Achse als Geraden ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q} paarweise orthogonalen lateinischen Quadraten (MOLS = mutually orthogonal Latin squares) der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} kann man ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (q+2,n)} -Netz erzeugen. Jedes der lateinischen Quadrate bestimmt die Inzidenzrelation für die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^2\,} Punkte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} - bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} Parallelenscharen eines Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (r,n)} -Netzes eine Liste von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r-2\,} MOLS der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} . Daher gilt: Ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (r,n)} -Netz existiert genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r-2\leq R(n)} ist. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R(n)} , die Folge der größtmöglichen Anzahlen von paarweise orthogonalen lateinischen Quadraten der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , ist Folge A001438 in OEIS.

Konstruktion aus kleineren Netzen

Aus einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (r,m)} - und einem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (r,n)} -Netz lässt sich stets ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (r,m\cdot n)} -Netz konstruieren. 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{N}} lässt sich eine solche digitale Signatur realisieren:

• Die möglichen Datensätze sind die r Parallelenscharen des Netzes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{N}} ,
• die möglichen Schlüssel sind die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^2} Punkte des Netzes
• und die gesendeten Nachrichten sind Geraden von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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, dass jedes perfekte Authentifikationssystem von einem Netz bestimmt wird. Die größtmögliche Anzahl an möglichen Datensätzen erhält man für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.