Neue Übersetzung für Problem 857

Hinweise zur Erstellung von Übersetzungen

Als Basis für jede Übersetzung dient der Text von projecteuler.net.
Der Originaltitel und Text im untenstehenden Formular sind zu übersetzen.
Der HTML-Quelltext in seiner Struktur sollte im Allgemeinen unverändert bleiben.
Querverweise zu anderen Problemen sollten in der Form /problem=?? erfolgen.
Wenn Grafiken oder Dateien verwendet werden, sollte die URL https://projecteuler.net/... verwendet werden.
Die Sie-Form benutzen.

Titel

Inhalt

A graph is made up of vertices and coloured edges. 
Between every two distinct vertices there must be exactly one of the following:

<ul>
<li>A red directed edge one way, and a blue directed edge the other way</li>
<li>A green undirected edge</li>
<li>A brown undirected edge</li>
</ul>

Such a graph is called beautiful if

<ul>
<li>A cycle of edges contains a red edge if and only if it also contains a blue edge</li>
<li>No triangle of edges is made up of entirely green or entirely brown edges</li>
</ul>

Below are four distinct examples of beautiful graphs on three vertices:

<img src="resources/images/0857_GoodGraphs.jpg?1692412187" alt="0857_GoodGraphs.jpg">

Below are four examples of graphs that are not beautiful:
<img src="resources/images/0857_BadGraphs.jpg?1692412205" alt="0857_BadGraphs.jpg">

Let $G(n)$ be the number of beautiful graphs on the labelled vertices: $1,2,\ldots,n$.
You are given $G(3)=24$, $G(4)=186$ and $G(15)=12472315010483328$.

Find $G(10^7)$. Give your answer modulo $10^9+7$.

​x
 
<p>A graph is made up of vertices and coloured edges. Between every two distinct vertices there must be exactly one of the following:</p>​<ul><li>A red directed edge one way, and a blue directed edge the other way</li><li>A green undirected edge</li><li>A brown undirected edge</li></ul>​Such a graph is called <i>beautiful</i> if ​<ul><li>A cycle of edges contains a red edge <b>if and only if</b> it also contains a blue edge</li><li>No triangle of edges is made up of entirely green or entirely brown edges</li></ul>​<p>Below are four distinct examples of beautiful graphs on three vertices:</p><img src="resources/images/0857_GoodGraphs.jpg?1692412187" alt="0857_GoodGraphs.jpg">​<p>Below are four examples of graphs that are not beautiful:</p><img src="resources/images/0857_BadGraphs.jpg?1692412205" alt="0857_BadGraphs.jpg">​<p>Let $G(n)$ be the number of beautiful graphs on the labelled vertices: $1,2,\ldots,n$.You are given $G(3)=24$, $G(4)=186$ and $G(15)=12472315010483328$.</p>​<p>Find $G(10^7)$. Give your answer modulo $10^9+7$.</p>

Sie erklären sich einverstanden, dass die Übersetzung unter der Creative Commons Lizenz CC BY-NC-SA 4.0 veröffentlicht wird. Wenn Sie wollen, dass die Übersetzung Ihnen zugeordnet werden kann, müssen Sie sich einloggen (oben rechts), andernfalls ist sie anonym.