(グラフ理論) 魔法陣グルグルの魔法陣は一筆書きが出来るか検証してみた 

# はじめに

こんにちは，Umamusume22です．記事の投稿が遅くなってしまい申し訳ありません．今回は魔法陣グルグルという漫画に出てくる魔法陣は一筆書きが出来るかを検証します．
　魔法陣グルグルは主人公の二ケとククリが魔王打倒のために冒険するストーリーです．月間少年ガンガンに1992年から2003年にかけて連載されました．2017年でもアニメ放送をやっていました[1]．
DMMで観ました．面白いアニメです．実家に漫画もあります．

https://www.ganganonline.com/title/25


　　　　　　　　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/4f55c84f-e6ca-9d6d-44c9-5682e65716cd.png)


出典："SQUARE ENIX"，https://magazine.jp.square-enix.com/top/anime/detail/guruguru/


# 一筆書きの定義[2,3]
一筆書きとは全ての辺を1回ずつ通る連続的な曲線を書くことができることを指します．一筆書きはグラフ理論です．グラフはいくつかの点とそれらを結ぶ線で構成される図形です．グラフの辺は頂点以外で交差しません．それぞれの辺の両端はいずれかの頂点で終わります．
また，グラフが連結であるか否かの判断はグラフのどの２つの頂点を選択しても辺を辿って片方の頂点からもう一方の頂点へ行けるかです．

一筆書きは二つの定義があります．

### 1つ目：オイラーグラフ
 一筆書きして出発点(始点)に戻って来ることができるグラフ．つまり，全ての辺を1回だけ通過して元に戻れるようなグラフのことです．

### 2つ目：準オイラーグラフ
　一筆書きすることはできるが出発点(始点)に戻って来ることができないグラフ．つまり，始点と終点が異なります．　以下の図が参考になります．
 
 　オイラーグラフでは始点からスタートして他の頂点を通過して始点に戻って来ることができます．ところが，準オイラーグラフでは始点からスタートして他の頂点を通過しても始点に戻って来ることができません．


　　　　　　　　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/619fed0f-2bd7-923c-939e-227236c00d4a.png)

出典："オイラーグラフの定理（一筆書きできる条件）とその証明"
https://manabitimes.jp/math/642




また，各頂点において，その頂点から出ている辺の本数をその**頂点の次数**と呼びます．つまり，頂点Aから出ている辺が3つであれば頂点Aの次数は３となります．この時，次数が奇数であればその頂点を**奇点**と呼び，偶数であれば**偶点**と呼びます．


# 検証に用いた魔法陣[4]

## 魔法陣：トーラ
　　　　　　　　　　　　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/8ba80e63-7432-40bb-f394-57b21b36f59e.png)
出典："魔法陣紹介！"，https://hp.vector.co.jp/authors/VA019204/guru/mahouzin.htm

上記の図形はトーラです．一番簡単な火の魔法です．魔法陣に垂直に火が出ます．
以下はトーラを使う時のシーンです．懐かしいシーンです．絵柄的に初期ですね．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/3bb75e25-2b6d-9131-4759-55436c73c94c.png)
出典："魔法陣グルグルの魔法・グルグル・キラキラまとめ"，https://renote.net/articles/7732

### トーラの検証結果[2]
　　　　　　　　　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/1666af57-07ee-f6d5-4865-b953a608990e.png" width="40%" >

#### 頂点の数：３つ
- 偶点：3つ
- 奇点：0つ

#### 一筆書き：成功
#### グラフの特徴：オイラーグラフ
トーラはオイラーグラフで一筆書きは成功しました．また，全ての頂点は偶点でした．トーラに引いている青い線は著者が一筆書きしたものです．青い線を見る限り，同じ辺を通過している箇所がありません．
<br><br>

## 魔法陣：トカゲのシッポ
　　　　　　　　　　　　　　![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/8ba3fd41-ddb6-7d4c-568e-118d3a211e1d.png)
出典："魔法陣紹介！"，https://hp.vector.co.jp/authors/VA019204/guru/mahouzin.htm

続いてトカゲのシッポです．トーラの円上に二つの直線を入れたものがトカゲのシッポです．
<br>

 <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/370a18b7-ea53-9f4b-c239-979c13922e73.png" width ="100%">
出典："ピクシブ百科事典"，https://dic.pixiv.net/a/%E3%83%88%E3%82%AB%E3%82%B2%E3%81%AE%E3%81%97%E3%81%A3%E3%81%BD


これもトーラと同じく火の呪文です．敵を倒します．ストーリーの最初の方で出てくる呪文です．著者が魔法陣グルグルを漫画で読んだ時，一番印象に残った呪文です．魔法陣グルグルといえばトカゲのシッポです．トカゲのシッポーーーーーーーーーーーーーーーー！

### トカゲのシッポの検証結果[2]
　　　　　　　　　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/964975/6842e6d8-5ded-f509-c313-6d8906d15ddb.png" width="40%" >

#### 頂点の数：9つ
- 偶点：5つ
- 奇点：4つ

#### 一筆書き：失敗
トカゲのシッポの場合，一筆書きはできませんでした．円と円の内側の三角形は２回通過することがなく，順調に青い線を引くことができました．しかし，円上に引いている２つの直線を引く場合はどうしても２回通過せざるを得ませんでした．

# 考察[2,3,5]
　トーラの場合はオイラーグラフで一筆書きに成功しました．しかし，トカゲのシッポの場合は失敗しました．トーラでは全ての頂点が偶数ですがトカゲのシッポは奇点が４つ存在します．
恐らく，全ての頂点が偶数でなければオイラーグラフとして成立しないことが推測されます．調べたところ，オイラーグラフの条件として奇点が0個でなければなりませんでした．一方，準オイラーグラフでは2個の奇点が条件です[2,3,5]．
今回，二つの呪文を検証しましたが確かに奇点が0個であるトーラはオイラーグラフであることが確認されました．

# 最後に
　今回の記事では魔法陣グルグルの魔法陣を対象に一筆書きが出来るか検証しました．トーラは一筆書きに成功しましたがトカゲのシッポは失敗しました．トーラやトカゲのシッポは魔法陣グルグルの最初に登場する呪文です．他にもヘビイチゴやれんがのおうちなど多数の魔法陣が存在します．
　他に存在する魔法陣は今回検証した魔法陣より複雑なグラフになっているのもあります．今後は他の魔法陣のグラフを検証し，自動でオイラーグラフであるか判定するソースコードも書きたいと思います．

ここまで記事を読んでいただきありがとうございました！
<br><br>



※ウマ娘の声をフーリエ変換した記事や水栓の開閉判定をLineに通知する記事も書いています．suzuが私です．興味がある方はぜひご覧ください！
https://vigne-cla.com/31-1/#toc5

※noteも始めました．
https://note.com/madoka235/n/nbba2153326e1

ぜひフォローよろしくお願いします!

# 参考文献
[1] "魔法陣グルグル"　https://ja.wikipedia.org/wiki/%E9%AD%94%E6%B3%95%E9%99%A3%E3%82%B0%E3%83%AB%E3%82%B0%E3%83%AB

[2]　"「一筆書きできますか？」"
https://www.cc.kyoto-su.ac.jp/~isida/Pdfs/06OC-L.pdf

[3] "オイラーグラフの定理（一筆書きできる条件）とその証明"
https://manabitimes.jp/math/642

[4] "魔法陣紹介！"
https://hp.vector.co.jp/authors/VA019204/guru/mahouzin.htm

[5] "うさぎでもわかる離散数学（グラフ理論）　第10羽　一筆書きができるかの簡単な見つけ方・オイラーグラフ・ハミルトングラフ"
https://www.momoyama-usagi.com/entry/math-risan10