<commit_before>===========
Das Theorem
===========

*****************
Umgangssprachlich
*****************

Die Frage mit der sich das Theorem beschäftigt ist, wie viele Kanten kann man maximal in einem ungerichteten Graphen mit n Knoten einbringen ohne das ein ein p Knoten großer Kreis entsteht.

************
Definitionen
************

Ungerichteter Graph
"""""""""""""""""""
Sei der ungerichtete Graph G definiert als Knotenmenge V

.. math::  V = \{ v_1, ..., v_n \}

und Kantenmenge E, wobei zwei Knoten :math:`v_i, v_j` benachbart sind falls

.. math::  (v_i, v_j) \in E

Ordnung des Graphen
"""""""""""""""""""""""

.. todo:: nachfragen ob Notation G(E) korrekt ist

Ein Graph G hat die Ordnung n, wenn G(E) aus n Kanten besteht. In diesem Fall wird G auch als :math:`G_n` benannt.


p-Kreis (p-clique) von Graph G
""""""""""""""""""""""""""""""

Dies ist ein vollständiger Untergraph von G der Ordnung p, also ein Graph K für dessen Knotenmenge V' gilt

.. math::  \forall v \in V': v \in V

wobei V die Knotenmenge von G ist. Für die Kantenmenge E' gilt in ähnlicher Weise

.. math::  \forall e \in E': e \in E

wobei E die Kantenmenge von G ist.

*******************
Turáns Graphtheorem
*******************

Turáns Graphtheorem besagt, dass für einen Graph G = (V,E) mit n Kanten ohne p-Kreis gilt:

.. math:: \mid E \mid \le (1- \frac{1}{p-1}) \frac{n^2}{2}<commit_msg>added sentence about start value for p<commit_after>===========
Das Theorem
===========

*****************
Umgangssprachlich
*****************

Die Frage mit der sich das Theorem beschäftigt ist, wie viele Kanten kann man maximal in einem ungerichteten Graphen mit n Knoten einbringen ohne das ein ein p Knoten großer Kreis entsteht.

************
Definitionen
************

Ungerichteter Graph
"""""""""""""""""""
Sei der ungerichtete Graph G definiert als Knotenmenge V

.. math::  V = \{ v_1, ..., v_n \}

und Kantenmenge E, wobei zwei Knoten :math:`v_i, v_j` benachbart sind falls

.. math::  (v_i, v_j) \in E

Ordnung des Graphen
"""""""""""""""""""""""

.. todo:: nachfragen ob Notation G(E) korrekt ist

Ein Graph G hat die Ordnung n, wenn G(E) aus n Kanten besteht. In diesem Fall wird G auch als :math:`G_n` benannt.


p-Kreis (p-clique) von Graph G
""""""""""""""""""""""""""""""

Dies ist ein vollständiger Untergraph von G der Ordnung p, also ein Graph K für dessen Knotenmenge V' gilt

.. math::  \forall v \in V': v \in V

wobei V die Knotenmenge von G ist. Für die Kantenmenge E' gilt in ähnlicher Weise

.. math::  \forall e \in E': e \in E

wobei E die Kantenmenge von G ist.

*******************
Turáns Graphtheorem
*******************

Turáns Graphtheorem besagt, dass für einen Graph G = (V,E) mit n Kanten ohne p-Kreis gilt:

.. math:: \mid E \mid \le (1- \frac{1}{p-1}) \frac{n^2}{2}

Hierbei muss p allerdings größer 1 sein, da wir ansonsten durch 0 teilen würden und da ein 1 Knoten großer Kreis sich schon durch die Definition von Kanten und Kreisen ausschließt.
{'fraction_non_alphanumeric': 0.1988540613414223, 'fraction_numerical': 0.005055611729019211, 'mean_word_length': 4.117241379310345, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '763835', 'n_tokens_mistral': 1112, 'n_tokens_neox': 1122, 'n_words': 410}