グラフ理論

ホフマンシングルトングラフはグラフのなかでもキャラだちしている（と思う） でも何故か、遠景のほうが拡大したイメージよりカッコいい。 ja.wikipedia.org 比較してみよう。 小さいイメージのほうが断然、ばえる。見栄えする。 ちなみに、最大にバエる特殊なグラフは、頂点162。辺が4536もある Local mclaughlin graphだろう。 自分のマシンでは計算できないが、最大にバエるのはこちらのWikiだ、 fr.wikipedia.org 今回判明したのだが、フランスは数学大国だね。特殊のグラフの多数のアーカイブがWikiにあるわ！ 英語版はそりゃ大量であっても当たり前だけど…

この五角形を埋め込んだ強正則グラフを加工して、商標化できるだろうか？ ja.wikipedia.org グラフ理論 丸善出版 Amazon グラフ理論入門(原書第4版) 作者:ウィルソン R. J. 近代科学社 Amazon

競技プログラミングでは「グラフの閉路検出」は頻出です。 しかし，解法が複数あるため，実践において時々どうアプローチしようか迷ったりすることがあります（個人的に......）。 本記事では，本番で適当な方法を選択できるように「無向・有向グラフにおける閉路検出方法」についてまとめます。 無向グラフ 方法(1)：DFS（深さ優先探索） 方法(2)：Union-Find 有向グラフ 方法(3)：トポロジカルソート 参考文献 無向グラフ 無向グラフにおいて，閉路がないグラフは，木である連結成分が1つまたは複数（森）ある状態です。 方法(1)：DFS（深さ優先探索） ある連結成分において，任意の頂点を根と…

Index Index グラフ理論 グラフとは 点 点の次数 / Degree 次数列 / Degree Sequence 孤立点 / Isolated Vertex 端点 / End Vertex 辺 多重辺 / multiple Edge Loop 歩道 (Walk) / 道 (Path) / 閉路 (Cycle) グラフの種類 単純グラフ vs 一般グラフ 単純グラフ / Simple Graph 一般グラフ / General Graph 無向グラフ vs 有向グラフ 無向グラフ / Undirected Graph 有向グラフ / Directed Graph ラベル付きグラフ / …

こんにちは. ぱいです. さて, 前回の記事で, 下記問題 (東大の 2022 年度入試) に登場する数列 の一般項について解説しました. 第 2 問 数列 を次のように定める。 \begin{align} a_{1} = 1, \quad a_{n+1} = a_{n}^{2} + 1 \quad ( n = 1, \ 2, \ 3, \ \cdots \cdots ) \end{align} (1) 正の整数 が 3 の倍数のとき, は 5 の倍数となることを示せ。 (2) , を正の整数とする。 が の倍数となるための必要十分条件を , を用いて表せ。 (3) と の最大公約数を求めよ。…

前回の記事の続きです。 astrostory.hatenablog.com この記事ではマルコフ連鎖をグラフとして見ていきます。なお、今回も例は前回の記事の天気の例を利用します。 簡単に再度説明しますと 晴れ、曇り、雨という3つの状態があり、そのいずれかの状態から別の状態に遷移します。 遷移の確率はそれぞれいかになります。 晴れ→晴れの確率をp1、曇り→晴れの確率をq1、雨→晴れの確率をr1 晴れ→曇りの確率をp2、曇り→曇りの確率をq2、雨→曇りの確率をr2 晴れ→雨の確率をp3、曇り→雨の確率をq3、雨→雨の確率をr3 グラフとして見る マルコフ連鎖をグラフとして見ると以下のようになります…

マルコフ連鎖というグラフ理論を用いた確率の考え方があり、これはプログラムの実装も可能で便利だと思うのでこの記事で詳しく説明できればと思います。 いつものように数学的な厳密性は少し欠けていても分かりやすい記事を目指します。 マルコフ連鎖とは マルコフ連鎖とはt(時間)が離散的なマルコフ過程の一種です。 マルコフ過程とは、次に起こる事象が今と過去の状態に依存することなく、現在の状態のみで決まる確率過程のことをいいます。 現在も状況のみで決まるというポイントが確率の表記を簡単に、コンピューターサイエンスに応用しやすくしているポイントだと思います。 実際にマルコフ連鎖を表現する数式は以下のように記述す…

グラフ理論といえば「ケーニヒスベルクの架け橋」や「オイラー」などのキーワードが浮かびますが、オイラー以外にもグラフ理論の発展に貢献した人物がいます。その一人が今回ご紹介するアイルランドの数学者、ハミルトンです。 今回はそんなハミルトンについて、グラフ理論をはじめとする数学で残した功績をご紹介します。

最近、自分の数学に対する理解がいい加減過ぎるなと思って嫌な気分になることが多い。雑にしか勉強してないもぐりだなと思う。 なんなら夢に見る。なぜか大学ではなくて高校にいて、ひたすら試験の勉強をするけど上手くいかない夢。数学がおろそかになっていた自覚があるのでそのせいだろうなと思っている。 たとえば、「P=NP 問題とは？」と訊かれたら私は答えることができるし、どういう問題なのか説明できる。*1 昔記事で書いたように、これは「多項式時間で解の正しさが検証できる判定問題のクラス」と「多項式時間で解を求められる判定問題のクラス」が一致しているかという問題だ。 seasawher.hatenablog.…

タイトル: ADHDを持つ子供のexecutive タイトル: 小児精神疾患のためのゲーム化されたデジタルメンタルヘルス介入の有効性：系統的レビューとメタ分析。 Perceived Chronic Traumatic Encephalopathy and Suicidality in Former タイトル: ADHDを持つ人々のための誠実性評価：測定特性と潜在的問題 Neurovascular dysfunction in psychiatric disorders: Underlying Assessment of BDNF and sialic acid levels in childr…

競技プログラミングマラソンコンテスト参加体験記 はじめに 私は最近、競技プログラミングのマラソンコンテストに参加しました。このコンテストは、与えられた時間内に効率的かつ最適なアルゴリズムを設計・実装することが求められるもので、技術力と問題解決能力が試されます。今回の体験記では、私が直面した課題とその解決方法、さらにOpenAIのChatGPTとの協力によって得られた学びについて詳しく紹介します。 コンテストの概要 今回のコンテストでは、以下のような問題が出題されました： 問題概要: 複数の点（炭酸飲料の座標）が与えられ、それらをすべて接続するための操作を決定します。操作は、既存の点から新しい点…

読者の皆様，ご無沙汰しております．社長です．早いことに２０２４年も前半戦が終了してしまったので，ちょっと遅めの振り返りです！ 創業５年目 ちょっと時間がたってしまいましたが，２０２４年７月に４年目の決算報告を提出完了し，ついに創業から５年目に突入しました！ただただ幸運と，よいお客様に恵まれたおかげです．感謝です！！ 毎年決算報告書を提出する度に悦に浸ってるんですが，下の写真，当社の決算報告書の表紙です．なんかちょっとカッコよくないですか？トヨタもアサヒビールも表紙は同じようなフォーマットです！中の数値は全然違いますけど（笑） ２０２３年度決算報告書！ 大学生活 ～ ２０２４年前期 東京理科大学…

こんにちは。 今回は「幅優先探索」と「深さ優先探索」を扱ってみます。 以前、迷路をつくったり、解いたり、迷路の形が雷の軌跡のモデルになるらしいと聞いて実際にやってみたりしました。 taq.hatenadiary.jp taq.hatenadiary.jp 1つ目の記事で迷路を解く方法として、行き止まりを埋めていくもの (言わば穴埋め法？) を実装してみました。 そんなある種外道なやり方だけ取りあげて、有名な幅優先探索や深さ優先探索はノータッチでしたので今回やってみます。 はじめてのように書いていますが、改めて読んでみたら雷の軌跡の件で幅優先探索だけやっていたようです。 2年前にちょろっと触れた…

記事 記事名:クイズ王・伊沢拓司 運転免許の筆記試験に不満爆発「僕よりできない人が作ってる」 リンク:https://news.yahoo.co.jp/articles/38fe81235f884b3c1a41a7c03889c3405ed645fe 一言感想 いっそのことQuizKnockが試験問題作ったら?

高専から阪大工学部電子情報工学科の情報通信工学科目に編入したaomidroです。阪大工学部に編入して前期が終了し、振り返りも兼ねて編入後の生活や、受けた講義などについて書いていきます。 入学式 編入生のガイダンス 単位認定について 履修について 各科目について 量子論基礎 符号理論 信号とシステム 情報社会と工学倫理 確率統計 機械学習とデータ処理及び演習 量子コンピューティング及び演習 数学解析演習 システム線形代数 実験B コンパイラ 情報システム工学演習Ⅰ 電磁気学Ⅰ 成績 一人暮らしについて サークル バイト 奨学金について 個人的にやってたこと 編入前にやるべきだと思ったこと 感想 …

数学の研究分野って、たくさんありますよね。三角関数や円グラフ、二次方程式や行列…学生時代にいろいろなテーマの勉強をしましたが、縦のつながりや横のつながりがつかみにくく、何のために勉強しているのか、これを覚えれば何に役立つのかがわからなかったものです。 そこで今回は数学の分野を大まかに分けてみました。各分野がどのようなことを研究しているのか把握できれば、数学界を俯瞰できます。「なるほどー、こういう研究が数学の一部を形成しているんだ」とわかれば、数学に対する理解が少し深まるはず…！

やりたいこと 書籍やネットーワーク上のリソース、音楽の音源などを自分の感覚で繋いで、仕事や趣味で利用できるか試してみようと思いました。 メモやノートでできるかもしれないけど、せっかくシステムを作る仕事をしているので、自分用のシステムを作ってみようと思い、設計を始めました。 このシステムのキーになるデータ構造が双方向リンク、グラフ理論で言うと完全グラフを実現することが必要で、使いなれたLaravelと、Ruby on Railsで実現しようと思いました。LaravelとRailsで実装する理由は、個人的な興味で、同じ機能を、異なるプログラミング言語、フレームワークで実装するとどんな差異が現れるの…

こんにちは。ファームウェアエンジニアインターン生の後藤です。 ちなみに以下の記事を書いた後藤さんとは違う後藤です。 engineering.nature.global 時が立つのは非常に早いもので、入社してから10ヶ月ほど立ったみたいです。 今年度で就職のため、ちょうど折り返し地点に来ました。 そこで中間報告として、新しくインターンに入るか迷っている方をターゲットに、入ったきっかけ、この会社のいいところ、コードレビューで学んだことを書いていこうと思います。 以下目次 入ろうと思ったきっかけ Natureエンジニアインターンのいいところ シフトが自由 実際のプロダクトコードが見れる 経験豊富なエ…