論文の概要: Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Education

• arxiv url: http://arxiv.org/abs/2602.05059v1
• Date: Wed, 04 Feb 2026 21:20:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.623865
• Title: Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Education
• Title（参考訳）: グラフ理論における解決・未解決問題に対する大規模言語モデルの評価:コンピューティング教育における意味
• Authors: Adithya Kulkarni, Mohna Chakraborty, Jay Bagga,
• Abstract要約: 大規模言語モデルは、コンピュータ科学の先進的な材料を探究するために学生によってますます使われている。 本研究では,2つのグラフ理論問題に対する LLM の性能について検討する。
• 参考スコア（独自算出の注目度）: 4.64684924758613
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models are increasingly used by students to explore advanced material in computer science, including graph theory. As these tools become integrated into undergraduate and graduate coursework, it is important to understand how reliably they support mathematically rigorous thinking. This study examines the performance of a LLM on two related graph theoretic problems: a solved problem concerning the gracefulness of line graphs and an open problem for which no solution is currently known. We use an eight stage evaluation protocol that reflects authentic mathematical inquiry, including interpretation, exploration, strategy formation, and proof construction. The model performed strongly on the solved problem, producing correct definitions, identifying relevant structures, recalling appropriate results without hallucination, and constructing a valid proof confirmed by a graph theory expert. For the open problem, the model generated coherent interpretations and plausible exploratory strategies but did not advance toward a solution. It did not fabricate results and instead acknowledged uncertainty, which is consistent with the explicit prompting instructions that directed the model to avoid inventing theorems or unsupported claims. These findings indicate that LLMs can support exploration of established material but remain limited in tasks requiring novel mathematical insight or critical structural reasoning. For computing education, this distinction highlights the importance of guiding students to use LLMs for conceptual exploration while relying on independent verification and rigorous argumentation for formal problem solving.
• Abstract（参考訳）: 大規模言語モデルは、グラフ理論を含むコンピュータ科学の先進的な材料を探究するために、学生によってますます使われてきている。 これらのツールが学部・大学院のコースワークに統合されるにつれて、数学的に厳密な思考をいかに確実に支援するかを理解することが重要である。 本研究では,線グラフの優雅性に関する解問題と,解が現在知られていない開問題という,関連する2つのグラフ理論上の LLM の性能について検討する。 我々は,解釈,探索,戦略形成,証明構築など,真正な数学的探究を反映した8段階評価プロトコルを用いる。 このモデルは、解答問題に強く取り組み、正しい定義を作成し、関連する構造を特定し、幻覚のない適切な結果を思い出し、グラフ理論の専門家によって確認された有効な証明を構築した。 オープンな問題に対して、モデルはコヒーレントな解釈と妥当な探索戦略を生み出したが、解に向かっては進まなかった。 結果は作成されず、不確実性を認めたが、これは定理や否定された主張の発明を避けるようモデルに指示する明示的なプロンプト命令と一致している。 これらの結果から, LLMは確立された物質の探索を支援できるが, 新しい数学的洞察や重要な構造的推論を必要とするタスクには限定的であることが示唆された。 コンピューティング教育において、この区別は、正式な問題解決に独立した検証と厳密な議論を頼りながら、概念探索にLLMを使うことを学生に指導することの重要性を強調している。

関連論文リスト

• Interpretability Framework for LLMs in Undergraduate Calculus [0.0]
  大規模言語モデル(LLM)は、教育においてますます使われているが、その正確性だけでは、彼らの問題解決行動の品質、信頼性、教育的妥当性を捉えていない。 本稿では,LLM生成解を代表領域として用いた新しい解釈可能性フレームワークを提案する。 提案手法は, 推論フロー抽出と解を意味ラベル付き操作や概念に分解し, 即時アブレーション解析と組み合わせて, 入力サリエンスと出力安定性を評価する。
  論文  参考訳（メタデータ） (2025-10-19T17:20:36Z)
• Large Language Models and Mathematical Reasoning Failures [1.6114012813668932]
  本稿では,50の高校レベルの単語問題を用いた大規模言語モデル(LLM)の数学的推論能力について検討する。 最終回答と解決手順の両方を厳格に分析して、推論の失敗を特定します。 より新しいモデル(例えば、o3-mini、deepseek-r1)はより精度が高いが、全てのモデルは空間的推論、戦略的計画、算術における誤りを示す。
  論文  参考訳（メタデータ） (2025-02-17T09:07:32Z)
• Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning [73.2950349728376]
  大規模言語モデル(LLM)は、幅広いタスクで顕著な成功を収めている。 しかし、彼らは情報片間の関係を理解し、推論する必要があるタスクの推論において、依然として課題に直面している。 この課題は、論理的推論やマルチホップ質問応答など、多段階プロセスに関わるタスクにおいて特に顕著である。 本稿では、まず文脈から明示的なグラフを構築することにより、グラフを用いた推論(RwG)を提案する。
  論文  参考訳（メタデータ） (2025-01-14T05:18:20Z)
• LLM-based Cognitive Models of Students with Misconceptions [55.29525439159345]
  本稿では,この2つの要件を満たすためにLLM(Large Language Models)を命令調整できるかどうかを検討する。 真正な学生ソリューションパターンを反映したデータセットを生成する新しいPythonライブラリであるMalAlgoPyを紹介する。 我々の洞察は、AIに基づく学生モデルの理解を高め、効果的な適応学習システムへの道を開く。
  論文  参考訳（メタデータ） (2024-10-16T06:51:09Z)
• Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path [53.71787069694794]
  大規模言語モデル(LLM)のグラフ推論能力に着目する。 グラフ記述変換,グラフ接続,最短パス問題という3つの基本グラフタスクにおけるLLMの能力を再考する。 この結果から,LLMはテキスト記述によるグラフ構造理解に失敗し,これらの基本課題に対して様々な性能を示すことが可能であることが示唆された。
  論文  参考訳（メタデータ） (2024-08-18T16:26:39Z)
• LLMs can Find Mathematical Reasoning Mistakes by Pedagogical Chain-of-Thought [28.122761006724925]
  PedCoT(Pedagogical Chain-of-Thought)は、推論ミスの識別のガイドとして設計されている。 PedCoTは、プロンプト(PPP)設計のための教育原則、2段階インタラクションプロセス(TIP)およびグラウンドドPedCoTプロンプトからなる。 提案手法は,信頼性の高い数学的誤り識別の目標を達成し,自動解答グレーディングの基盤を提供する。
  論文  参考訳（メタデータ） (2024-05-09T07:37:34Z)
• Do Language Models Exhibit the Same Cognitive Biases in Problem Solving as Human Learners? [140.9751389452011]
  本研究では,大言語モデル(LLM)の偏りを,算術語問題を解く際に,子どもに知られているものと関連づけて検討する。 我々は,これらの各テストに対して,問題特徴のきめ細かい制御を可能にするニューロシンボリックアプローチを用いて,新しい単語問題を生成する。
  論文  参考訳（メタデータ） (2024-01-31T18:48:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。