[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/114947#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/114947","headline":"\u30b0\u30e9\u30d5\u7406\u8ad6 &#8211; Wikipedia","name":"\u30b0\u30e9\u30d5\u7406\u8ad6 &#8211; Wikipedia","description":"\u30b0\u30e9\u30d5\u7406\u8ad6\uff08\u30b0\u30e9\u30d5\u308a\u308d\u3093\u3001\u82f1: Graph theory\uff09\u306f\u3001\u30ce\u30fc\u30c9\uff08\u7bc0\u70b9\u30fb\u9802\u70b9\u3001\u70b9\uff09\u306e\u96c6\u5408\u3068\u30a8\u30c3\u30b8\uff08\u679d\u30fb\u8fba\u3001\u7dda\uff09\u306e\u96c6\u5408\u3067\u69cb\u6210\u3055\u308c\u308b\u30b0\u30e9\u30d5\u306b\u95a2\u3059\u308b\u6570\u5b66\u306e\u7406\u8ad6\u3067\u3042\u308b\u3002 \u30b0\u30e9\u30d5\uff08\u30c7\u30fc\u30bf\u69cb\u9020\uff09\u306a\u3069\u306e\u5fdc\u7528\u304c\u3042\u308b\u3002 \u30b0\u30e9\u30d5\u306b\u3088\u3063\u3066\u3001\u69d8\u3005\u306a\u3082\u306e\u306e\u95a2\u9023\u3092\u8868\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002 6\u3064\u306e\u7bc0\u70b9\u30687\u3064\u306e\u8fba\u304b\u3089\u6210\u308b\u30b0\u30e9\u30d5\u306e\u4e00\u4f8b \u4f8b\u3048\u3070\u3001\u9244\u9053\u3084\u8def\u7dda\u30d0\u30b9\u7b49\u306e\u8def\u7dda\u56f3\u3092\u8003\u3048\u308b\u969b\u306b\u306f\u3001\u99c5\uff08\u7bc0\u70b9\uff09\u304c\u3069\u306e\u3088\u3046\u306b\u8def\u7dda\uff08\u8fba\uff09\u3067\u7d50\u3070\u308c\u3066\u3044\u308b\u304b\u304c\u554f\u984c\u3068\u306a\u308b\u4e00\u65b9\u3001\u7dda\u8def\u304c\u5177\u4f53\u7684\u306b\u3069\u306e\u3088\u3046\u306a\u66f2\u7dda\u3092\u63cf\u3044\u3066\u3044\u308b\u304b\u306f\u672c\u8cea\u7684\u306a\u554f\u984c\u3068\u306a\u3089\u306a\u3044\u3053\u3068\u304c\u591a\u3044\u3002 \u3057\u305f\u304c\u3063\u3066\u3001\u8def\u7dda\u56f3\u3067\u306f\u99c5\u9593\u306e\u8ddd\u96e2\u3084\u5fae\u5999\u306a\u914d\u7f6e\u3001\u8def\u7dda\u306e\u5f62\u72b6\u306a\u3069\u304c\u3057\u3070\u3057\u3070\u5730\u7406\u4e0a\u306e\u5b9f\u969b\u3068\u306f\u7570\u306a\u3063\u3066\u63cf\u304b\u308c\u3066\u3044\u308b\u3002\u3064\u307e\u308a\u3001\u8def\u7dda\u56f3\u306e\u5229\u7528\u8005\u306b\u3068\u3063\u3066\u306f\u3001\u99c5\u3068\u99c5\u306e\u300c\u3064\u306a\u304c\u308a\u65b9\u300d\u304c\u4e3b\u306b\u91cd\u8981\u306a\u60c5\u5831\u306a\u306e\u3067\u3042\u308b\u3002 \u3053\u306e\u3088\u3046\u306b\u3001\u300c\u3064\u306a\u304c\u308a\u65b9\u300d\u306b\u7740\u76ee\u3057\u3066\u62bd\u8c61\u5316\u3055\u308c\u305f\u300c\u70b9\u3068\u305d\u308c\u3089\u3092\u3080\u3059\u3076\u7dda\u300d\u306e\u6982\u5ff5\u304c\u30b0\u30e9\u30d5\u3067\u3042\u308a[1]\u3001\u30b0\u30e9\u30d5\u304c\u3082\u3064\u69d8\u3005\u306a\u6027\u8cea\u3092\u63a2\u6c42\u3059\u308b\u306e\u304c\u30b0\u30e9\u30d5\u7406\u8ad6\u3067\u3042\u308b\u3002 \u3064\u306a\u304c\u308a\u65b9\u3060\u3051\u3067\u306f\u306a\u304f\u300c\u3069\u3061\u3089\u304b\u3089\u3069\u3061\u3089\u306b\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u304b\u300d\u3092\u3082\u554f\u984c\u306b\u3059\u308b\u5834\u5408\u3001\u30a8\u30c3\u30b8\u306b\u77e2\u5370\u3092\u3064\u3051\u308b\u3002\u3053\u306e\u3088\u3046\u306a\u30b0\u30e9\u30d5\u3092\u6709\u5411\u30b0\u30e9\u30d5\u3001\u307e\u305f\u306f\u3001\u30c0\u30a4\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002\u77e2\u5370\u306e\u306a\u3044\u30b0\u30e9\u30d5\u306f\u3001\u7121\u5411\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002 \u30b0\u30e9\u30d5\u3092\u8868\u73fe\u3059\u308b\u306e\u306b\u3001\u56f3\u3067\u306f\u306a\u304f\u3001\u96a3\u63a5\u884c\u5217\u3092\u7528\u3044\u308b\u3053\u3068\u304c\u3042\u308b\u3002\u7121\u5411\u30b0\u30e9\u30d5\u306e\u96a3\u63a5\u884c\u5217\u306f\u3001\u5bfe\u79f0\u884c\u5217\u306b\u306a\u308b\u3002\u4f8b\u3048\u3070\u3001\u4e0a\u306e\u30b0\u30e9\u30d5\u306f\u3001\u6b21\u306e\u96a3\u63a5\u884c\u5217\u3067\u8868\u73fe\u3067\u304d\u308b\u3002 (010010101010010100001011110100000100){displaystyle {begin{pmatrix}0&#038;1&#038;0&#038;0&#038;1&#038;0\\1&#038;0&#038;1&#038;0&#038;1&#038;0\\0&#038;1&#038;0&#038;1&#038;0&#038;0\\0&#038;0&#038;1&#038;0&#038;1&#038;1\\1&#038;1&#038;0&#038;1&#038;0&#038;0\\0&#038;0&#038;0&#038;1&#038;0&#038;0\\end{pmatrix}}} Table of Contents \u30b0\u30e9\u30d5\u306e\u4f8b[\u7de8\u96c6]\u5f62\u5f0f\u7684\u306a\u5b9a\u7fa9[\u7de8\u96c6]\u6709\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]\u7121\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]\u9802\u70b9\u3068\u8fba[\u7de8\u96c6]\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5[\u7de8\u96c6]\u63a5\u5408\u3068\u96a3\u63a5[\u7de8\u96c6]\u8ddd\u96e2\u3068\u76f4\u5f84[\u7de8\u96c6]\u30eb\u30fc\u30d7\u3068\u591a\u91cd\u30b0\u30e9\u30d5[\u7de8\u96c6]\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u62e1\u5927\u30b0\u30e9\u30d5[\u7de8\u96c6]\u6b21\u6570\u3068\u6b63\u5247\u30b0\u30e9\u30d5[\u7de8\u96c6]\u9053\u3068\u9589\u8def[\u7de8\u96c6]\u5b8c\u5168\u30b0\u30e9\u30d5\u3068\u30af\u30ea\u30fc\u30af[\u7de8\u96c6]\u305d\u306e\u4ed6\u306e\u7528\u8a9e[\u7de8\u96c6]\u8a08\u7b97\u6a5f\u79d1\u5b66[\u7de8\u96c6]\u8a00\u8a9e\u5b66[\u7de8\u96c6]\u7269\u7406\u5b66\u304a\u3088\u3073\u5316\u5b66[\u7de8\u96c6]\u793e\u4f1a\u79d1\u5b66[\u7de8\u96c6]\u751f\u7269\u5b66[\u7de8\u96c6]\u6570\u5b66[\u7de8\u96c6]\u305d\u306e\u4ed6[\u7de8\u96c6]\u554f\u984c\u3068\u5b9a\u7406[\u7de8\u96c6]\u51fa\u5178\u3068\u88dc\u8db3[\u7de8\u96c6]\u53c2\u8003\u6587\u732e[\u7de8\u96c6]\u95a2\u9023\u6587\u732e[\u7de8\u96c6]\u65e5\u672c\u8a9e\u306e\u6587\u732e[\u7de8\u96c6]\u65e5\u672c\u8a9e\u4ee5\u5916[\u7de8\u96c6]\u95a2\u9023\u9805\u76ee[\u7de8\u96c6]\u5916\u90e8\u30ea\u30f3\u30af[\u7de8\u96c6] \u30b0\u30e9\u30d5\u306e\u4f8b[\u7de8\u96c6] \u65e5\u5e38\u7684\u306a\u554f\u984c\u3084\u5de5\u5b66\u7684\u554f\u984c\u306e\u591a\u304f\u3092\u30b0\u30e9\u30d5\u3068\u3057\u3066\u8003\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002 \u8def\u7dda\u56f3:","datePublished":"2022-03-18","dateModified":"2022-03-18","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/author\/lordneo#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/author\/lordneo","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/11\/book.png","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/11\/book.png","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/5\/5b\/6n-graf.svg\/333px-6n-graf.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/5\/5b\/6n-graf.svg\/333px-6n-graf.svg.png","height":"220","width":"333"},"url":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/114947","about":["Wiki"],"wordCount":10481,"articleBody":"\u30b0\u30e9\u30d5\u7406\u8ad6\uff08\u30b0\u30e9\u30d5\u308a\u308d\u3093\u3001\u82f1: Graph theory\uff09\u306f\u3001\u30ce\u30fc\u30c9\uff08\u7bc0\u70b9\u30fb\u9802\u70b9\u3001\u70b9\uff09\u306e\u96c6\u5408\u3068\u30a8\u30c3\u30b8\uff08\u679d\u30fb\u8fba\u3001\u7dda\uff09\u306e\u96c6\u5408\u3067\u69cb\u6210\u3055\u308c\u308b\u30b0\u30e9\u30d5\u306b\u95a2\u3059\u308b\u6570\u5b66\u306e\u7406\u8ad6\u3067\u3042\u308b\u3002\u30b0\u30e9\u30d5\uff08\u30c7\u30fc\u30bf\u69cb\u9020\uff09\u306a\u3069\u306e\u5fdc\u7528\u304c\u3042\u308b\u3002\u30b0\u30e9\u30d5\u306b\u3088\u3063\u3066\u3001\u69d8\u3005\u306a\u3082\u306e\u306e\u95a2\u9023\u3092\u8868\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002  6\u3064\u306e\u7bc0\u70b9\u30687\u3064\u306e\u8fba\u304b\u3089\u6210\u308b\u30b0\u30e9\u30d5\u306e\u4e00\u4f8b\u4f8b\u3048\u3070\u3001\u9244\u9053\u3084\u8def\u7dda\u30d0\u30b9\u7b49\u306e\u8def\u7dda\u56f3\u3092\u8003\u3048\u308b\u969b\u306b\u306f\u3001\u99c5\uff08\u7bc0\u70b9\uff09\u304c\u3069\u306e\u3088\u3046\u306b\u8def\u7dda\uff08\u8fba\uff09\u3067\u7d50\u3070\u308c\u3066\u3044\u308b\u304b\u304c\u554f\u984c\u3068\u306a\u308b\u4e00\u65b9\u3001\u7dda\u8def\u304c\u5177\u4f53\u7684\u306b\u3069\u306e\u3088\u3046\u306a\u66f2\u7dda\u3092\u63cf\u3044\u3066\u3044\u308b\u304b\u306f\u672c\u8cea\u7684\u306a\u554f\u984c\u3068\u306a\u3089\u306a\u3044\u3053\u3068\u304c\u591a\u3044\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u8def\u7dda\u56f3\u3067\u306f\u99c5\u9593\u306e\u8ddd\u96e2\u3084\u5fae\u5999\u306a\u914d\u7f6e\u3001\u8def\u7dda\u306e\u5f62\u72b6\u306a\u3069\u304c\u3057\u3070\u3057\u3070\u5730\u7406\u4e0a\u306e\u5b9f\u969b\u3068\u306f\u7570\u306a\u3063\u3066\u63cf\u304b\u308c\u3066\u3044\u308b\u3002\u3064\u307e\u308a\u3001\u8def\u7dda\u56f3\u306e\u5229\u7528\u8005\u306b\u3068\u3063\u3066\u306f\u3001\u99c5\u3068\u99c5\u306e\u300c\u3064\u306a\u304c\u308a\u65b9\u300d\u304c\u4e3b\u306b\u91cd\u8981\u306a\u60c5\u5831\u306a\u306e\u3067\u3042\u308b\u3002\u3053\u306e\u3088\u3046\u306b\u3001\u300c\u3064\u306a\u304c\u308a\u65b9\u300d\u306b\u7740\u76ee\u3057\u3066\u62bd\u8c61\u5316\u3055\u308c\u305f\u300c\u70b9\u3068\u305d\u308c\u3089\u3092\u3080\u3059\u3076\u7dda\u300d\u306e\u6982\u5ff5\u304c\u30b0\u30e9\u30d5\u3067\u3042\u308a[1]\u3001\u30b0\u30e9\u30d5\u304c\u3082\u3064\u69d8\u3005\u306a\u6027\u8cea\u3092\u63a2\u6c42\u3059\u308b\u306e\u304c\u30b0\u30e9\u30d5\u7406\u8ad6\u3067\u3042\u308b\u3002\u3064\u306a\u304c\u308a\u65b9\u3060\u3051\u3067\u306f\u306a\u304f\u300c\u3069\u3061\u3089\u304b\u3089\u3069\u3061\u3089\u306b\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u304b\u300d\u3092\u3082\u554f\u984c\u306b\u3059\u308b\u5834\u5408\u3001\u30a8\u30c3\u30b8\u306b\u77e2\u5370\u3092\u3064\u3051\u308b\u3002\u3053\u306e\u3088\u3046\u306a\u30b0\u30e9\u30d5\u3092\u6709\u5411\u30b0\u30e9\u30d5\u3001\u307e\u305f\u306f\u3001\u30c0\u30a4\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002\u77e2\u5370\u306e\u306a\u3044\u30b0\u30e9\u30d5\u306f\u3001\u7121\u5411\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002\u30b0\u30e9\u30d5\u3092\u8868\u73fe\u3059\u308b\u306e\u306b\u3001\u56f3\u3067\u306f\u306a\u304f\u3001\u96a3\u63a5\u884c\u5217\u3092\u7528\u3044\u308b\u3053\u3068\u304c\u3042\u308b\u3002\u7121\u5411\u30b0\u30e9\u30d5\u306e\u96a3\u63a5\u884c\u5217\u306f\u3001\u5bfe\u79f0\u884c\u5217\u306b\u306a\u308b\u3002\u4f8b\u3048\u3070\u3001\u4e0a\u306e\u30b0\u30e9\u30d5\u306f\u3001\u6b21\u306e\u96a3\u63a5\u884c\u5217\u3067\u8868\u73fe\u3067\u304d\u308b\u3002(010010101010010100001011110100000100){displaystyle {begin{pmatrix}0&#038;1&#038;0&#038;0&#038;1&#038;0\\1&#038;0&#038;1&#038;0&#038;1&#038;0\\0&#038;1&#038;0&#038;1&#038;0&#038;0\\0&#038;0&#038;1&#038;0&#038;1&#038;1\\1&#038;1&#038;0&#038;1&#038;0&#038;0\\0&#038;0&#038;0&#038;1&#038;0&#038;0\\end{pmatrix}}}Table of Contents\u30b0\u30e9\u30d5\u306e\u4f8b[\u7de8\u96c6]\u5f62\u5f0f\u7684\u306a\u5b9a\u7fa9[\u7de8\u96c6]\u6709\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]\u7121\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]\u9802\u70b9\u3068\u8fba[\u7de8\u96c6]\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5[\u7de8\u96c6]\u63a5\u5408\u3068\u96a3\u63a5[\u7de8\u96c6]\u8ddd\u96e2\u3068\u76f4\u5f84[\u7de8\u96c6]\u30eb\u30fc\u30d7\u3068\u591a\u91cd\u30b0\u30e9\u30d5[\u7de8\u96c6]\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u62e1\u5927\u30b0\u30e9\u30d5[\u7de8\u96c6]\u6b21\u6570\u3068\u6b63\u5247\u30b0\u30e9\u30d5[\u7de8\u96c6]\u9053\u3068\u9589\u8def[\u7de8\u96c6]\u5b8c\u5168\u30b0\u30e9\u30d5\u3068\u30af\u30ea\u30fc\u30af[\u7de8\u96c6]\u305d\u306e\u4ed6\u306e\u7528\u8a9e[\u7de8\u96c6]\u8a08\u7b97\u6a5f\u79d1\u5b66[\u7de8\u96c6]\u8a00\u8a9e\u5b66[\u7de8\u96c6]\u7269\u7406\u5b66\u304a\u3088\u3073\u5316\u5b66[\u7de8\u96c6]\u793e\u4f1a\u79d1\u5b66[\u7de8\u96c6]\u751f\u7269\u5b66[\u7de8\u96c6]\u6570\u5b66[\u7de8\u96c6]\u305d\u306e\u4ed6[\u7de8\u96c6]\u554f\u984c\u3068\u5b9a\u7406[\u7de8\u96c6]\u51fa\u5178\u3068\u88dc\u8db3[\u7de8\u96c6]\u53c2\u8003\u6587\u732e[\u7de8\u96c6]\u95a2\u9023\u6587\u732e[\u7de8\u96c6]\u65e5\u672c\u8a9e\u306e\u6587\u732e[\u7de8\u96c6]\u65e5\u672c\u8a9e\u4ee5\u5916[\u7de8\u96c6]\u95a2\u9023\u9805\u76ee[\u7de8\u96c6]\u5916\u90e8\u30ea\u30f3\u30af[\u7de8\u96c6]\u30b0\u30e9\u30d5\u306e\u4f8b[\u7de8\u96c6]\u65e5\u5e38\u7684\u306a\u554f\u984c\u3084\u5de5\u5b66\u7684\u554f\u984c\u306e\u591a\u304f\u3092\u30b0\u30e9\u30d5\u3068\u3057\u3066\u8003\u3048\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u8def\u7dda\u56f3: \u524d\u7bc0\u306e\u3068\u304a\u308a\u3002\u96fb\u6c17\u56de\u8def: \u56de\u8def\u56f3\u3092\u66f8\u304f\u5834\u5408\u3001\u5b9f\u969b\u306e\u30ea\u30fc\u30c9\u7dda\u3069\u304a\u308a\u306e\u5f62\u72b6\u306b\u56f3\u3092\u63cf\u3044\u305f\u308a\u306f\u3057\u306a\u3044\u3002\u3053\u306e\u5834\u5408\u3082\u3001\u300c\u63a5\u70b9\u304c\u3069\u3046\u3064\u306a\u304c\u3063\u3066\u3044\u308b\u304b\u300d\u3060\u3051\u304c\u554f\u984c\u3067\u3042\u3063\u3066\u3001\u300c\u3064\u306a\u304c\u308a\u65b9\u300d\u3092\u4fdd\u3061\u3064\u3064\u3067\u304d\u308b\u3060\u3051\u898b\u3084\u3059\u3044\u5f62\u306b\u7d75\u3092\u63cf\u304f\u3002\u56de\u8def\u56f3\u306f\u4e00\u7a2e\u306e\u30b0\u30e9\u30d5\u3067\u3042\u308b\u3002WWW\u306e\u69cb\u9020: WWW\u306b\u304a\u3051\u308b\u30a6\u30a7\u30d6\u30da\u30fc\u30b8\u306e\u3001\u30cf\u30a4\u30d1\u30fc\u30ea\u30f3\u30af\u30fb\u88ab\u30ea\u30f3\u30af\u95a2\u4fc2\u304c\u306a\u3059\u69cb\u9020\u306f\u3001\u6709\u5411\u30b0\u30e9\u30d5\u306e\u4e00\u7a2e\u3067\u3042\u308b[2]\u3002  \u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u30011736\u5e74\u306b\u300c\u30b1\u30fc\u30cb\u30d2\u30b9\u30d9\u30eb\u30af\u306e\u554f\u984c\u300d\u3068\u547c\u3070\u308c\u308b\u30d1\u30ba\u30eb\u306b\u5bfe\u3057\u3066\u30aa\u30a4\u30e9\u30fc\u304c\u89e3\u6cd5\u3092\u793a\u3057\u305f[3][4]\u306e\u304c\u8d77\u6e90\u306e\u3072\u3068\u3064\u3068\u3055\u308c\u308b[5]\u3002\u3053\u306e\u554f\u984c\u306f\u3001\u4e00\u7b46\u66f8\u304d\u3068\u6df1\u304f\u95a2\u9023\u3057\u3066\u3044\u308b[6]\u3002\u5f62\u5f0f\u7684\u306a\u5b9a\u7fa9[\u7de8\u96c6]\u6709\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]\u96c6\u5408 V , E \u3068\u3001E \u306e\u5143\uff08\u3052\u3093\u3001\u8981\u7d20\uff09\u306b\u3001\u4e8c\u3064\u306e V \u3092\u5143\u306e\u5bfe\u3067\u5bfe\u5fdc\u3055\u305b\u308b\u5199\u50cff:\u00a0E\u2192V\u00d7V{displaystyle fcolon  Eto Vtimes V}\u306e\u4e09\u3064\u7d44  G:=(f,V,E){displaystyle G:=(f,V,E)}\u3092\u6709\u5411\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002V \u306e\u5143\u3092 G \u306e\u9802\u70b9\u307e\u305f\u306f\u30ce\u30fc\u30c9\u3001E \u306e\u5143\u3092 G \u306e\u8fba\u307e\u305f\u306f\u5f27\u3068\u547c\u3076\u3002f(e)=(v, v)\u3068\u306a\u308be\u2208E\u306f\u30eb\u30fc\u30d7\u306b\u5bfe\u5fdc\u3057\u3001f(a)=f(b)\u3068\u306a\u308ba,b\u2208E\u306f\u591a\u91cd\u8fba\u306b\u5bfe\u5fdc\u3059\u308b\u3002\u7121\u5411\u30b0\u30e9\u30d5[\u7de8\u96c6]P(V) \u3092 V \u306e\u51aa\u96c6\u5408\u3068\u3059\u308b\u3002E \u306e\u5143\u306b V \u306e \u90e8\u5206\u96c6\u5408\u3092\u5bfe\u5fdc\u3055\u305b\u308b\u5199\u50cf  g:\u00a0E\u2192P(V){displaystyle gcolon  Eto P(V)}\u304c\u3042\u3063\u3066\u3001E \u306e\u4efb\u610f\u306e\u5143 e \u306b\u3064\u3044\u3066\u3001e \u306e\u50cf g(e) \u306e\u6fc3\u5ea6\u304c1\u307e\u305f\u306f2\u3067\u3042\u308b\u3068\u304d\u3001\u4e09\u3064\u7d44G:=(g,V,E){displaystyle G:=(g,V,E)}\u3092\u7121\u5411\u30b0\u30e9\u30d5\u3068\u3044\u3046[7]\u3002V \u306e\u5143\u3092 G \u306e\u9802\u70b9\u3001E \u306e\u5143\u3092 G \u306e\u8fba\u3068\u547c\u3076\u3002 g(e)\u306e\u6fc3\u5ea6\u304c1\u3068\u306a\u308be\u2208E\u306f\u30eb\u30fc\u30d7\u306b\u5bfe\u5fdc\u3057\u3001g(a)=g(b)\u3068\u306a\u308ba,b\u2208E\u306f\u591a\u91cd\u8fba\u306b\u5bfe\u5fdc\u3059\u308b\u3002\u5358\u7d14\u30b0\u30e9\u30d5\u306b\u9650\u3063\u3066\u8a00\u3048\u3070\u3001E \u3092\u6700\u521d\u304b\u3089\u3042\u308b\u96c6\u5408\u306e\u90e8\u5206\u96c6\u5408\u3068\u8003\u3048\u3001\u5199\u50cf\u3092\u7528\u3044\u305a\u306b\u30b0\u30e9\u30d5\u3092\u5b9a\u7fa9\u3059\u308b\u3053\u3068\u3082\u3067\u304d\u308b\uff1a\u6709\u5411\u30b0\u30e9\u30d5\u3067\u306f\u3001E \u3092 V\u00d7V \u306e\u90e8\u5206\u96c6\u5408\u3001\u7121\u5411\u30b0\u30e9\u30d5\u3067\u306f\u3001E \u3092 P(V) \u306e\u90e8\u5206\u96c6\u5408\u3067\u30012\u3064\u306e\u5143\u306e\u96c6\u5408\u3060\u3051\u304b\u3089\u306a\u308b\u3082\u306e\u3068\u3059\u308c\u3070\u3088\u3044\u3002\u4ee5\u4e0b\u3067\u306f\u5358\u306b\u30b0\u30e9\u30d5\u3068\u3044\u3063\u305f\u6642\u306b\u306f\u7121\u5411\u30b0\u30e9\u30d5\u3092\u6307\u3059\u3002\u9802\u70b9\u3068\u8fba[\u7de8\u96c6]\u9802\u70b9\u306e\u96c6\u5408\u306fV{displaystyle V}\u3001\u8fba\u306e\u96c6\u5408\u306fE{displaystyle E}\u3067\u8868\u3059\u3002\u30b0\u30e9\u30d5G{displaystyle G}\u304c\u5148\u306b\u4e0e\u3048\u3089\u308c\u3066\u3044\u308b\u5834\u5408\u306b\u306f\u3001\u9802\u70b9\u96c6\u5408\u3092V(G){displaystyle V(G)}\u3001\u8fba\u96c6\u5408\u3092E(G){displaystyle E(G)} \u3068\u8868\u3059\u3053\u3068\u3082\u3042\u308b[8]\u3002\u6570\u5b66\u4ee5\u5916\u306e\u5206\u91ce\u3067\u306f\u3001\u9802\u70b9\u3092\u7bc0\u70b9\u3001\u8fba\u3092\u679d\u3068\u547c\u3076\u3053\u3068\u304c\u591a\u3044\u3002\u8fba\u3092\u5f27\u3084\u30ea\u30f3\u30af\u3068\u547c\u3076\u3053\u3068\u3082\u3042\u308b\u3002\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5[\u7de8\u96c6]\u30b0\u30e9\u30d5\u306e\u8fba\u306b\u91cd\u307f\uff08\u30b3\u30b9\u30c8\uff09\u304c\u4ed8\u3044\u3066\u3044\u308b\u30b0\u30e9\u30d5\u3092\u3001\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5\u3068\u547c\u3076\u3002\u4e57\u63db\u6848\u5185\u56f3\u306e\u5834\u5408\u3001\u99c5\u9593\u306e\u6240\u8981\u6642\u9593\u304c\u300c\u91cd\u307f\u300d\u306b\u3042\u305f\u308b\u3002\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5\u306f\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u3068\u3082\u547c\u3070\u308c\u308b\uff08\u30d5\u30ed\u30fc\u30cd\u30c3\u30c8\u30ef\u30fc\u30af, \u30d9\u30a4\u30b8\u30a2\u30f3\u30cd\u30c3\u30c8\u30ef\u30fc\u30af, \u30cb\u30e5\u30fc\u30e9\u30eb\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u306a\u3069\uff09\u3002\u63a5\u5408\u3068\u96a3\u63a5[\u7de8\u96c6]\u8fbae{displaystyle e}\u306e\u4e21\u7aef\u306e\u70b9\u3092\u7aef\u70b9\u3068\u3044\u3044\u3001\u7aef\u70b9\u306f\u8fbae{displaystyle e}\u306b\u63a5\u5408\uff08\u307e\u305f\u306f\u63a5\u7d9a\uff09\u3057\u3066\u3044\u308b\u3068\u3044\u3046\u3002\u307e\u305f\u3001\u8fba\u3068\u8fba\u304c\u3042\u308b\u9802\u70b9\u3092\u5171\u6709\u3057\u3066\u3044\u308b\u3068\u304d\u3001\u305d\u306e\u8fba\u3069\u3046\u3057\u306f\u96a3\u63a5\u3057\u3066\u3044\u308b\u3068\u3044\u3046[8]\u3002\u8ddd\u96e2\u3068\u76f4\u5f84[\u7de8\u96c6]2\u9802\u70b9\u9593\uff08\u96a3\u63a5\u3057\u3066\u3044\u308b\u5fc5\u8981\u306f\u306a\u3044\uff09\u3092\u7d4c\u7531\u3059\u308b\u8fba\u6570\u3092\u9577\u3055\u3068\u547c\u3073\u3001\u7279\u306b\u6700\u77ed\u7d4c\u8def\u306b\u304a\u3051\u308b\u8fba\u6570\u3092\u8ddd\u96e2\u3068\u547c\u3076\u3002\u30b0\u30e9\u30d5 G \u306e\u6700\u5927\u9802\u70b9\u9593\u8ddd\u96e2\u3092\u76f4\u5f84\u3068\u547c\u3073\u3001diam(G) \u3068\u8868\u3059\u3002\u30eb\u30fc\u30d7\u3068\u591a\u91cd\u30b0\u30e9\u30d5[\u7de8\u96c6]\u3042\u308b\u8fba\u306e\u4e21\u7aef\u70b9\u304c\u7b49\u3057\u3044\u3068\u304d\u3001\u30eb\u30fc\u30d7\uff08\u81ea\u5df1\u30eb\u30fc\u30d7\uff09\u3068\u3044\u3046\u3002\u307e\u305f\u30012\u9802\u70b9\u9593\u306b\u8907\u6570\u306e\u8fba\u304c\u3042\u308b\u3068\u304d\u3001\u591a\u91cd\u8fba\u3068\u3044\u3046\u3002\u30eb\u30fc\u30d7\u3082\u591a\u91cd\u8fba\u3082\u542b\u307e\u306a\u3044\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u5358\u7d14\u30b0\u30e9\u30d5\u3068\u3044\u3044\u3001\u30eb\u30fc\u30d7\u3084\u591a\u91cd\u8fba\u3092\u542b\u3080\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u591a\u91cd\u30b0\u30e9\u30d5\u3068\u3044\u3046[11]\u3002\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u62e1\u5927\u30b0\u30e9\u30d5[\u7de8\u96c6]  2\u3064\u306e\u30b0\u30e9\u30d5G{displaystyle G}\u3068G\u2032{displaystyle G&#8217;} \u306b\u3064\u3044\u3066\u3001G\u2032{displaystyle G&#8217;}\u306e\u9802\u70b9\u96c6\u5408\u3068\u8fba\u96c6\u5408\u304c\u5171\u306bG{displaystyle G}\u306e\u9802\u70b9\u96c6\u5408\u3068\u8fba\u96c6\u5408\u306e\u90e8\u5206\u96c6\u5408\u306b\u306a\u3063\u3066\u3044\u308b\u3068\u304d\u3001G\u2032{displaystyle G&#8217;}\u306fG{displaystyle G}\u306e\u90e8\u5206\u30b0\u30e9\u30d5\u3067\u3042\u308b\u3001\u307e\u305f\u306fG{displaystyle G}\u306fG\u2032{displaystyle G&#8217;} \u306e\u62e1\u5927\u30b0\u30e9\u30d5\u3067\u3042\u308b\u3068\u3044\u3044\u3001G\u2032\u2286G{displaystyle G&#8217;subseteq G}\u3068\u8868\u3059[8]\u3002\u7279\u306b\u3001G{displaystyle G}\u3068G\u2032{displaystyle G&#8217;}\u306e\u9802\u70b9\u96c6\u5408\u304c\u7b49\u3057\u3044\u3068\u304d\u3001G\u2032{displaystyle G&#8217;}\u306fG{displaystyle G}\u306e\u5168\u57df\u90e8\u5206\u30b0\u30e9\u30d5\u3067\u3042\u308b\u3068\u3044\u3046\u3002\u307e\u305f\u3001G{displaystyle G} \u306e\u9802\u70b9\u96c6\u5408 V{displaystyle V} \u306e\u90e8\u5206\u96c6\u5408 U{displaystyle U} \u3092\u53d6\u308a\u51fa\u3057\u3066\u3001\u4e21\u7aef\u70b9\u304c U{displaystyle U} \u306b\u5c5e\u3059\u308b\u5168\u3066\u306e\u8fba\u3092\u8fba\u96c6\u5408\u3068\u3059\u308b G \u306e\u90e8\u5206\u30b0\u30e9\u30d5 G[U]{displaystyle G[U]} \u3092\u3001\u8a98\u5c0e\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002\u30b0\u30e9\u30d5 G{displaystyle G} \u304b\u3089\u3042\u308b\u8fba e{displaystyle e} \u3092\u53d6\u308a\u9664\u304d\u3001\u305d\u306e\u8fba\u306e\u4e21\u7aef\u70b9\u3092\u4e00\u3064\u306e\u9802\u70b9\u306b\u307e\u3068\u3081\u308b\u3053\u3068\u3092\uff08\u8fba\u306e\uff09\u7e2e\u7d04\u3068\u3044\u3044\u3001\u7e2e\u7d04\u306e\u7d50\u679c\u5f97\u3089\u308c\u308b\u30b0\u30e9\u30d5\u3092 G\/e{displaystyle G\/e} \u3068\u8868\u3059\u3002\u306a\u304a\u3001\u8a98\u5c0e\u90e8\u5206\u30b0\u30e9\u30d5\u306e\u300c\u8a98\u5c0e\u300d\u306finduced\u306e\u8a33\u8a9e\u3067\u3042\u308b\u3002induce\u306e\u8a33\u3068\u3057\u3066\u306f\u3053\u306e\u300c\u8a98\u5c0e\u3059\u308b\u300d\u306e\u4ed6\u306b\u300c\u751f\u6210\u3059\u308b\u300d\u304c\u3042\u308b[12][13]\u3002\u3053\u306e\u305f\u3081\u3001\u8a98\u5c0e\u90e8\u5206\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u751f\u6210\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3053\u3068\u3082\u3042\u308b[14]\u3002\u4e00\u65b9\u3001\u751f\u6210\u90e8\u5206\u30b0\u30e9\u30d5\u306f\u5168\u57df\u90e8\u5206\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u6307\u3059\u3053\u3068\u3082\u3042\u308b\u3002\u3053\u306e\u305f\u3081\u3001\u751f\u6210\u90e8\u5206\u30b0\u30e9\u30d5\u3068\u3044\u3046\u8a9e\u3092\u4f7f\u3046\u969b\u306f\u3001\u6df7\u4e71\u304c\u306a\u3044\u304b\u6c17\u3092\u4ed8\u3051\u308b\u5fc5\u8981\u304c\u3042\u308b\u3002\u6b21\u6570\u3068\u6b63\u5247\u30b0\u30e9\u30d5[\u7de8\u96c6]  \u9802\u70b9 v{displaystyle v} \u306b\u63a5\u7d9a\u3059\u308b\u679d\u306e\u6570\u3092\u6b21\u6570\u3068\u3044\u3044\u3001d(v){displaystyle d(v)} \u3067\u8868\u3059\u3002\u6709\u5411\u30b0\u30e9\u30d5\u306b\u304a\u3044\u3066\u306f\u3001v{displaystyle v} \u306b\u5165\u3063\u3066\u304f\u308b\u8fba\u6570\u306e\u3053\u3068\u3092\u5165\u6b21\u6570\u3001v{displaystyle v} \u304b\u3089\u51fa\u3066\u884c\u304f\u8fba\u6570\u306e\u3053\u3068\u3092\u51fa\u6b21\u6570\u3068\u3044\u3046\u3002\u3059\u3079\u3066\u306e\u9802\u70b9\u304c\u540c\u6570\u306e\u96a3\u63a5\u70b9\u3001\u3064\u307e\u308a\u6b21\u6570\u3092\u3082\u3064\u30b0\u30e9\u30d5\u3092\u6b63\u5247\u30b0\u30e9\u30d5\u3068\u547c\u3076\u3002\u4efb\u610f\u306e\u9802\u70b9 v{displaystyle v} \u306b\u3064\u3044\u3066\u3001d(v)=k{displaystyle d(v)=k} \u304c\u6210\u308a\u7acb\u3064\u3068\u304d\u3001k -\u6b63\u5247\u3068\u3044\u3046\u3002k -\u6b63\u5247\u306a\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092k -\u6b63\u5247\u30b0\u30e9\u30d5\u3068\u3044\u3046\u3002\u30b0\u30e9\u30d5 G{displaystyle G} \u304c\u6301\u3064\u9802\u70b9\u306e\u6b21\u6570\u306e\u6700\u5c0f\u5024\u3092 \u03b4(G){displaystyle delta (G)}\u3001\u6700\u5927\u5024\u3092 \u0394(G){displaystyle Delta (G)} \u3067\u8868\u3059\u3002\u307e\u305f\u3001\u6b21\u6570 0 \u306e\u9802\u70b9\u306e\u3053\u3068\u3092\u5b64\u7acb\u70b9\u3068\u3044\u3046\u3002\u9053\u3068\u9589\u8def[\u7de8\u96c6]\u96a3\u63a5\u3057\u3066\u3044\u308b\u9802\u70b9\u540c\u58eb\u3092\u305f\u3069\u3063\u305f v0,\u00a0e0,\u00a0v1,\u00a0e1,...,\u00a0en\u22121,\u00a0vn{displaystyle v_{0},~e_{0},~v_{1},~e_{1},&#8230;,~e_{n-1},~v_{n}} \u306e\u7cfb\u5217\u3092\u9577\u3055 n (\u2265 0) \u306e\u6b69\u9053\uff08\u9396\u30fb\u30a6\u30a9\u30fc\u30af\uff09\u3068\u3044\u3046\u3002\u8fba\u306e\u91cd\u8907\u3092\u8a31\u3055\u306a\u3044\u6b69\u9053\u3092\u8def\uff08\u5c0f\u5f84\u30fb\u30c8\u30ec\u30a4\u30eb\uff09\u3068\u3044\u3046\u3002\u9802\u70b9\u306e\u91cd\u8907\u3092\u8a31\u3055\u306a\u3044\u5834\u5408\u3001\u3064\u307e\u308a\u3001\u4e21\u7aef\u306e2\u9802\u70b9\u306e\u6b21\u6570\u304c1\u3001\u305d\u308c\u4ee5\u5916\u306e\u3059\u3079\u3066\u306e\u9802\u70b9\u306e\u6b21\u6570\u304c2\u3067\u3042\u308b\u30b0\u30e9\u30d5\u3092\u3001\u9053\uff08\u30d1\u30b9\uff09\u3001\u958b\u3044\u305f\u6b69\u9053\u3092\u30d1\u30b9\u3068\u3044\u3046\u5834\u5408\u306f\u5358\u7d14\u30d1\u30b9\u3068\u3044\u3046\u3002\u307e\u305f\u3001\u59cb\u70b9\u3068\u7d42\u70b9\u304c\u540c\u3058\u8def\u306e\u3053\u3068\u3092\u9589\u8def\uff08\u56de\u8def\u30fb\u5faa\u74b0 \u30fb\u30b5\u30fc\u30ad\u30c3\u30c8\u3001\u30b5\u30a4\u30af\u30eb\uff09\u3001\u59cb\u70b9\u3068\u7d42\u70b9\u304c\u540c\u3058\u9053\uff08\u3064\u307e\u308ae1,\u00a0e2,\u00a0...,\u00a0en,\u00a0e1{displaystyle e_{1},~e_{2},~&#8230;,~e_{n},~e_{1}}\u3068\u3044\u3046\u8def\u3067ei\u00a0{displaystyle e_{i}~}\u304c\u76f8\u7570\u306a\u308b\u3082\u306e\uff09\u306e\u3053\u3068\u3092\u9589\u9053\uff08\u30b5\u30a4\u30af\u30eb\uff09\u3068\u3044\u3046[17]\u3002\u5b8c\u5168\u30b0\u30e9\u30d5\u3068\u30af\u30ea\u30fc\u30af[\u7de8\u96c6]  3\u9802\u70b9\u304b\u3089\u306a\u308b\u5b8c\u5168\u30b0\u30e9\u30d5\uff1a\u4e09\u89d2\u5f62\u4efb\u610f\u306e 2 \u9802\u70b9\u9593\u306b\u679d\u304c\u3042\u308b\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u5b8c\u5168\u30b0\u30e9\u30d5\uff08\u5b8c\u5099\u30b0\u30e9\u30d5\uff09\u3068\u3044\u3046[8][18]\u3002n{displaystyle n} \u9802\u70b9\u306e\u5b8c\u5168\u30b0\u30e9\u30d5\u306f\u3001Kn{displaystyle K_{n}} \u3067\u8868\u3059\u3002K3{displaystyle K_{3}} \u306f\u4e09\u89d2\u5f62\u3068\u547c\u3070\u308c\u308b\u3002\u307e\u305f\u3001\u5b8c\u5168\u30b0\u30e9\u30d5\u306b\u306a\u308b\u8a98\u5c0e\u90e8\u5206\u30b0\u30e9\u30d5\u306e\u3053\u3068\u3092\u30af\u30ea\u30fc\u30af\u3068\u3044\u3046\u3002\u5927\u304d\u3055\uff08\u30b5\u30a4\u30ba\uff09 n{displaystyle n} \u306e\u30af\u30ea\u30fc\u30af\u3092\u542b\u3080\u30b0\u30e9\u30d5\u306f\u300cn-\u30af\u30ea\u30fc\u30af\u3067\u3042\u308b\u300d\u3068\u3044\u3046\u3002\u8fba\u3092\u3082\u3064\u30b0\u30e9\u30d5\u306f\u5fc5\u305a2\u9802\u70b9\u306e\u5b8c\u5168\u30b0\u30e9\u30d5\u3092\u542b\u3080\u306e\u3067 2-\u30af\u30ea\u30fc\u30af\u3067\u3042\u308b\u3002\u307e\u305f n-\u30af\u30ea\u30fc\u30af\u3067\u3042\u3063\u3066\u3001\u76f4\u5f84\u304c n \u672a\u6e80\u3068\u306a\u308b\u30b0\u30e9\u30d5\u3092 n-\u30af\u30e9\u30f3\u3068\u3044\u3046\u3002\u305d\u306e\u4ed6\u306e\u7528\u8a9e[\u7de8\u96c6]  2013\u5e74\u306e\u590f\u306e1\u30ab\u6708\u306e\u9593\u306b\u7570\u306a\u308b\u8a00\u8a9e\u7248\u306eWikipedia\uff08\u9802\u70b9\uff09\u306b\u8ca2\u732e\u3057\u305fWikipedia\u7de8\u96c6\u8005\uff08\u8fba\uff09\u306b\u3088\u3063\u3066\u5f62\u6210\u3055\u308c\u305f\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u30b0\u30e9\u30d5[19]\u3002\u30b0\u30e9\u30d5\u306f\u7269\u7406\u5b66\u7684\u3001\u751f\u7269\u5b66\u7684[20][21]\u3001\u793e\u4f1a\u7684\u3001\u304a\u3088\u3073\u60c5\u5831\u30b7\u30b9\u30c6\u30e0\u306b\u304a\u3051\u308b\u591a\u304f\u306e\u7a2e\u985e\u306e\u95a2\u4fc2\u3068\u904e\u7a0b\u3092\u30e2\u30c7\u30eb\u5316\u3059\u308b\u305f\u3081\u306b\u4f7f\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u591a\u304f\u306e\u73fe\u5b9f\u7684\u554f\u984c\u306f\u30b0\u30e9\u30d5\u306b\u3088\u3063\u3066\u8868\u308f\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u73fe\u5b9f\u4e16\u754c\u306e\u30b7\u30b9\u30c6\u30e0\u3078\u306e\u5fdc\u7528\u3092\u5f37\u8abf\u3059\u308b\u6642\u306b\u306f\u3001\u300c\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u300d\u3068\u3044\u3046\u7528\u8a9e\u304c\u30b0\u30e9\u30d5\u3092\u610f\u5473\u3059\u308b\u305f\u3081\u306b\u5b9a\u7fa9\u3055\u308c\u308b\u3053\u3068\u304c\u3042\u308b\u3002\u3053\u306e\u30b0\u30e9\u30d5\u3067\u306f\u3001\u5c5e\u6027\uff08\u4f8b\u3048\u3070\u540d\u524d\uff09\u304c\u9802\u70b9\u304a\u3088\u3073\u8fba\u3068\u95a2\u9023\u4ed8\u3051\u3089\u308c\u308b\u3002\u73fe\u5b9f\u4e16\u754c\u306e\u30b7\u30b9\u30c6\u30e0\u3092\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u3068\u3057\u3066\u8868\u73fe\u3057\u7406\u89e3\u3059\u308b\u4e3b\u984c\u306f\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u79d1\u5b66\uff08\u82f1\u8a9e\u7248\uff09\u3068\u547c\u3070\u308c\u308b\u3002\u8a08\u7b97\u6a5f\u79d1\u5b66[\u7de8\u96c6]\u8a08\u7b97\u6a5f\u79d1\u5b66\u306b\u304a\u3044\u3066\u3001\u30b0\u30e9\u30d5\u306f\u30b3\u30df\u30e5\u30cb\u30b1\u30fc\u30b7\u30e7\u30f3\u3001\u30c7\u30fc\u30bf\u7de8\u6210\u3001\u8a08\u7b97\u88c5\u7f6e\u3001\u8a08\u7b97\u306e\u6d41\u308c\u7b49\u306e\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u3092\u8868\u308f\u3059\u305f\u3081\u306b\u4f7f\u308f\u308c\u308b\u3002\u4f8b\u3048\u3070\u3001\u30a6\u30a7\u30d6\u30b5\u30a4\u30c8\u306e\u30ea\u30f3\u30af\u69cb\u9020\u306f\u6709\u5411\u30b0\u30e9\u30d5\u3068\u3057\u3066\u8868\u308f\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3053\u3053\u3067\u306f\u3001\u9802\u70b9\u304c\u30a6\u30a7\u30d6\u30da\u30fc\u30b8\u3092\u8868\u308f\u3057\u3001\u6709\u5411\u8fba\u304c\u3042\u308b\u30da\u30fc\u30b8\u304b\u3089\u5225\u306e\u30da\u30fc\u30b8\u3078\u306e\u30ea\u30f3\u30af\u3092\u8868\u308f\u3059\u3002\u540c\u69d8\u306e\u30a2\u30d7\u30ed\u30fc\u30c1\u3092\u3001\u30bd\u30fc\u30b7\u30e3\u30eb\u30e1\u30c7\u30a3\u30a2[22]\u3001\u65c5\u884c\u3001\u751f\u7269\u5b66\u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30c1\u30c3\u30d7\u8a2d\u8a08\u3001\u795e\u7d4c\u5909\u6027\u75be\u60a3\u306e\u9032\u884c\u306e\u30de\u30c3\u30d4\u30f3\u30b0[23][24]\u3001\u305d\u3057\u3066\u305d\u306e\u4ed6\u591a\u304f\u306e\u5206\u91ce\u306b\u304a\u3051\u308b\u8ab2\u984c\u306b\u3064\u3044\u3066\u53d6\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u30b0\u30e9\u30d5\u3092\u53d6\u308a\u6271\u3046\u305f\u3081\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u958b\u767a\u304c\u8a08\u7b97\u6a5f\u79d1\u5b66\u306b\u304a\u3051\u308b\u4e3b\u8981\u306a\u8208\u5473\u3067\u3042\u308b\u3002\u30b0\u30e9\u30d5\u306e\u5909\u63db\uff08\u82f1\u8a9e\u7248\uff09\u306f\u30b0\u30e9\u30d5\u66f8\u63db\u3048\u7cfb\u306b\u3088\u3063\u3066\u3057\u3070\u3057\u3070\u5b9a\u5f0f\u5316\u3055\u308c\u3001\u8868\u73fe\u3055\u308c\u308b\u3002\u30b0\u30e9\u30d5\u5909\u63db\u7cfb\u3068\u76f8\u88dc\u7684\u306a\u30b0\u30e9\u30d5\u306e\u898f\u5247\u306b\u57fa\u3065\u304f\u30e1\u30e2\u30ea\u30fc\u5185\u64cd\u4f5c\u306b\u6ce8\u76ee\u3057\u305f\u30b7\u30b9\u30c6\u30e0\u304c\u3001\u30b0\u30e9\u30d5\u69cb\u9020\u3092\u6301\u3064\u30c7\u30fc\u30bf\u306e\u30c8\u30e9\u30f3\u30b6\u30af\u30b7\u30e7\u30f3\u30bb\u30fc\u30d5\u3067\u6c38\u7d9a\u7684\u306a\u683c\u7d0d\u3068\u554f\u3044\u5408\u308f\u305b\u306b\u5bfe\u5fdc\u3057\u305f\u30b0\u30e9\u30d5\u30c7\u30fc\u30bf\u30d9\u30fc\u30b9\uff08\u82f1\u8a9e\u7248\uff09\u3067\u3042\u308b\u3002\u8a00\u8a9e\u5b66[\u7de8\u96c6]\u69d8\u3005\u306a\u5f62\u5f0f\u306e\u30b0\u30e9\u30d5\u7406\u8ad6\u7684\u624b\u6cd5\u306f\u8a00\u8a9e\u5b66\u306b\u304a\u3044\u3066\u7279\u306b\u6709\u7528\u3067\u3042\u308b\u3053\u3068\u304c\u8a3c\u660e\u3055\u308c\u3066\u3044\u308b\u3002\u3053\u308c\u306f\u3001\u81ea\u7136\u8a00\u8a9e\u304c\u3057\u3070\u3057\u3070\u96e2\u6563\u69cb\u9020\u3078\u3068\u3088\u304f\u9069\u3057\u3066\u3044\u308b\u305f\u3081\u3067\u3042\u308b\u3002\u4f1d\u7d71\u7684\u306b\u3001\u7d71\u8a9e\u8ad6\u3068\u5408\u6210\u610f\u5473\u8ad6\u306f\u6728\u69cb\u9020\u306b\u5f93\u3044\u3001\u305d\u308c\u3089\u306e\u8868\u73fe\u529b\u306f\u3001\u968e\u5c64\u7684\u30b0\u30e9\u30d5\u306b\u3088\u3063\u3066\u30e2\u30c7\u30eb\u5316\u3055\u308c\u308b\u69cb\u6210\u6027\u306e\u539f\u7406\uff08\u82f1\u8a9e\u7248\uff09\u306b\u5bc6\u63a5\u306b\u95a2\u4fc2\u3059\u308b\u3002\u4e3b\u8f9e\u99c6\u52d5\u53e5\u69cb\u9020\u6587\u6cd5\u3068\u3044\u3063\u305f\u3088\u308a\u73fe\u4ee3\u7684\u306a\u624b\u6cd5\u306f\u578b\u4ed8\u304d\u7d20\u6027\u69cb\u9020\uff08\u3053\u308c\u306f\u6709\u5411\u975e\u5de1\u56de\u30b0\u30e9\u30d5\u3067\u3042\u308b\uff09\u3092\u7528\u3044\u3066\u81ea\u7136\u8a00\u8a9e\u306e\u69cb\u6587\u3092\u30e2\u30c7\u30eb\u5316\u3059\u308b\u3002\u8a9e\u5f59\u610f\u5473\u8ad6\u5185\u3001\u7279\u306b\u8a08\u7b97\u6a5f\u3078\u5fdc\u7528\u3068\u3057\u3066\u306f\u3001\u5358\u8a9e\u306e\u610f\u5473\u306e\u30e2\u30c7\u30eb\u5316\u306f\u3001\u4e0e\u3048\u3089\u308c\u305f\u5358\u8a9e\u304c\u95a2\u9023\u3059\u308b\u5358\u8a9e\u306e\u89b3\u70b9\u304b\u3089\u7406\u89e3\u3055\u308c\u308b\u6642\u306b\u3088\u308a\u5bb9\u6613\u3067\u3042\u308b\u3002\u3057\u305f\u304c\u3063\u3066\u610f\u5473\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u306f\u8a08\u7b97\u8a00\u8a9e\u5b66\u306b\u304a\u3044\u3066\u91cd\u8981\u3067\u3042\u308b\u3002\u4eca\u3067\u3001\u54f2\u5b66\uff08\u4f8b\u3048\u3070\u3001\u683c\u5b50\u30b0\u30e9\u30d5\uff08\u82f1\u8a9e\u7248\uff09\u3092\u7528\u3044\u308b\u6700\u9069\u6027\u7406\u8ad6\uff09\u3084\u5f62\u614b\u8ad6\uff08\u4f8b\u3048\u3070\u6709\u9650\u72b6\u614b\u30c8\u30e9\u30f3\u30b9\u30c7\u30e5\u30fc\u30b5\uff08\u82f1\u8a9e\u7248\uff09\u3092\u7528\u3044\u308b\u6709\u9650\u72b6\u614b\u5f62\u614b\u8ad6\uff09\u306b\u304a\u3051\u308b\u305d\u306e\u4ed6\u306e\u624b\u6cd5\u306f\u3001\u30b0\u30e9\u30d5\u3068\u3057\u3066\u306e\u8a00\u8a9e\u306e\u89e3\u6790\u306b\u304a\u3044\u3066\u4e00\u822c\u7684\u3067\u3042\u308b\u3002\u5b9f\u969b\u3001\u3053\u306e\u6570\u5b66\u306e\u5206\u91ce\u306e\u8a00\u8a9e\u5b66\u3078\u306e\u6709\u7528\u6027\u306f\u3001TextGraphs[25]\u3001WordNet\u3084VerbNet\uff08\u82f1\u8a9e\u7248\uff09\u3068\u3044\u3063\u305f\u69d8\u3005\u306a &#8220;Net&#8221; \u30d7\u30ed\u30b8\u30a7\u30af\u30c8\u306e\u3088\u3046\u306a\u7d44\u7e54\u3092\u751f\u3093\u3067\u304d\u305f\u3002\u7269\u7406\u5b66\u304a\u3088\u3073\u5316\u5b66[\u7de8\u96c6]\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u5316\u5b66\u304a\u3088\u3073\u7269\u7406\u5b66\u306b\u304a\u3044\u3066\u5206\u5b50\u3092\u7814\u7a76\u3059\u308b\u305f\u3081\u306b\u3082\u4f7f\u308f\u308c\u308b\u3002\u51dd\u7e2e\u7cfb\u7269\u7406\u5b66\u3067\u306f\u3001\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u3057\u305f\u8907\u96d1\u306a\u539f\u5b50\u69cb\u9020\u306e3\u6b21\u5143\u69cb\u9020\u306f\u3001\u539f\u5b50\u306e\u30c8\u30dd\u30ed\u30b8\u30fc\u306b\u95a2\u9023\u3057\u305f\u30b0\u30e9\u30d5\u7406\u8ad6\u7684\u6027\u8cea\u306b\u95a2\u3059\u308b\u7d71\u8a08\u91cf\u3092\u96c6\u3081\u308b\u3053\u3068\u306b\u3088\u3063\u3066\u5b9a\u91cf\u7684\u306b\u7814\u7a76\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u307e\u305f\u3001\u30d5\u30a1\u30a4\u30f3\u30de\u30f3\u306e\u8a08\u7b97\u306e\u30b0\u30e9\u30d5\u3068\u898f\u5247\u306f\u3001\u7406\u89e3\u3057\u305f\u3044\u5b9f\u9a13\u7684\u6570\u5b57\u3068\u5bc6\u63a5\u306b\u95a2\u4fc2\u3057\u305f\u5f62\u5f0f\u3067\u91cf\u5b50\u5834\u7406\u8ad6\u3092\u8981\u7d04\u3059\u308b[26]\u3002\u5316\u5b66\u3067\u306f\u3001\u30b0\u30e9\u30d5\u306f\u5206\u5b50\u306b\u3064\u3044\u3066\u306e\u81ea\u7136\u306a\u6a21\u578b\u3092\u4f5c\u308a\u3001\u3053\u3053\u3067\u306f\u9802\u70b9\u304c\u539f\u5b50\u3001\u8fba\u304c\u7d50\u5408\u3092\u8868\u308f\u3059\u3002\u3053\u306e\u30a2\u30d7\u30ed\u30fc\u30c1\u306f\u5206\u5b50\u69cb\u9020\u306e\u8a08\u7b97\u51e6\u7406\uff08\u5206\u5b50\u30a8\u30c7\u30a3\u30bf\u304b\u3089\u30c7\u30fc\u30bf\u30d9\u30fc\u30b9\u63a2\u7d22\u307e\u3067\uff09\u306b\u304a\u3044\u3066\u7279\u306b\u4f7f\u308f\u308c\u308b\u3002\u7d71\u8a08\u7269\u7406\u5b66\u3067\u306f\u3001\u30b0\u30e9\u30d5\u306f\u7cfb\u306e\u76f8\u4e92\u4f5c\u7528\u3057\u3066\u3044\u308b\u90e8\u4f4d\u9593\u306e\u5c40\u6240\u7684\u3064\u306a\u304c\u308a\u3084\u3001\u3053\u3046\u3044\u3063\u305f\u7cfb\u306b\u304a\u3051\u308b\u7269\u7406\u7684\u904e\u7a0b\u306e\u30c0\u30a4\u30ca\u30df\u30af\u30b9\u3092\u8868\u308f\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u540c\u69d8\u306b\u3001\u8a08\u7b97\u8ad6\u7684\u795e\u7d4c\u79d1\u5b66\u3067\u306f\u3001\u30b0\u30e9\u30d5\u306f\u69d8\u3005\u306a\u8a8d\u77e5\u904e\u7a0b\u3092\u751f\u3058\u3055\u305b\u308b\u305f\u3081\u306b\u76f8\u4e92\u4f5c\u7528\u3059\u308b\u8133\u9818\u57df\u9593\u306e\u6a5f\u80fd\u7684\u7d50\u5408\u3092\u8868\u308f\u3059\u305f\u3081\u306b\u4f7f\u3046\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3053\u3053\u3067\u306f\u3001\u9802\u70b9\u304c\u8133\u306e\u7570\u306a\u308b\u9818\u57df\u3092\u8868\u308f\u3057\u3001\u8fba\u304c\u305d\u308c\u3089\u306e\u9818\u57df\u9593\u306e\u7d50\u5408\u3092\u8868\u308f\u3059\u3002\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u96fb\u6c17\u56de\u8def\u7db2\u306e\u96fb\u6c17\u7684\u30e2\u30c7\u30ea\u30f3\u30b0\u306b\u304a\u3044\u3066\u91cd\u8981\u306a\u5f79\u5272\u3092\u679c\u305f\u3059\u3002\u3053\u3053\u3067\u3001\u91cd\u307f\u306f\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u69cb\u9020\u306e\u96fb\u6c17\u7684\u6027\u8cea\u3092\u5f97\u308b\u305f\u3081\u306b\u6709\u7dda\u90e8\u5206\u306e\u62b5\u6297\u3068\u95a2\u9023\u4ed8\u3051\u3089\u308c\u308b[27]\u3002\u30b0\u30e9\u30d5\u306f\u591a\u5b54\u8cea\u6750\u6599\u306e\u30df\u30af\u30ed\u30b9\u30b1\u30fc\u30eb\u30c1\u30e3\u30cd\u30eb\u3092\u8868\u308f\u3059\u3089\u305f\u3081\u306b\u4f7f\u3046\u3053\u3068\u3082\u3067\u304d\u308b\u3002\u3053\u3053\u3067\u306f\u3001\u9802\u70b9\u304c\u5b54\u3092\u8868\u308f\u3057\u3001\u8fba\u304c\u5b54\u9593\u3092\u3064\u306a\u3050\u3088\u308a\u5c0f\u3055\u306a\u30c1\u30e3\u30cd\u30eb\u3092\u8868\u308f\u3059\u3002\u5316\u5b66\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u5206\u5b50\u3092\u30e2\u30c7\u30eb\u5316\u3059\u308b\u624b\u6bb5\u3068\u3057\u3066\u5206\u5b50\u30b0\u30e9\u30d5\u3092\u4f7f\u7528\u3059\u308b\u3002\u793e\u4f1a\u79d1\u5b66[\u7de8\u96c6]  \u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u793e\u4f1a\u5b66\u306b\u304a\u3044\u3066\u3082\u3001\u4f8b\u3048\u3070\u3001\u7279\u306b\u793e\u4f1a\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u5206\u6790\u30bd\u30d5\u30c8\u30a6\u30a7\u30a2\u3092\u4f7f\u3063\u3066\u4ff3\u512a\u306e\u540d\u58f0\u3092\u898b\u7a4d\u3063\u305f\u308a\uff08\u82f1\u8a9e\u7248\uff09\u3001\u3046\u308f\u3055\u306e\u5e83\u304c\u308a\u3092\u8abf\u67fb\u3057\u305f\u308a\u3059\u308b\u624b\u6bb5\u3068\u3057\u3066\u5e83\u304f\u4f7f\u308f\u308c\u3066\u3044\u308b\u3002\u793e\u4f1a\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u306e\u5098\u306e\u4e0b\u306b\u3001\u591a\u304f\u306e\u7570\u306a\u308b\u7a2e\u985e\u306e\u30b0\u30e9\u30d5\u304c\u3042\u308b[29]\u3002\u77e5\u308a\u5408\u3044\u95a2\u4fc2\u30b0\u30e9\u30d5\u3068\u53cb\u60c5\u95a2\u4fc2\u30b0\u30e9\u30d5\u306f\u4eba\u3005\u304c\u77e5\u308a\u5408\u3044\u304b\u3069\u3046\u304b\u3092\u8a18\u8ff0\u3059\u308b\u3002\u5f71\u97ff\u30b0\u30e9\u30d5\u306f\u7279\u5b9a\u306e\u4eba\u3005\u304c\u4ed6\u8005\u306e\u632f\u308b\u821e\u3044\u306b\u5f71\u97ff\u3059\u308b\u304b\u3069\u3046\u304b\u3092\u30e2\u30c7\u30eb\u5316\u3059\u308b\u3002\u6700\u5f8c\u306b\u3001\u5354\u8abf\u30b0\u30e9\u30d5\u306f2\u4eba\u306e\u4eba\u7269\u304c\u3001\u6620\u753b\u3067\u4e00\u7dd2\u306b\u6f14\u6280\u3059\u308b\u3068\u3044\u3063\u305f\u3042\u308b\u7279\u5b9a\u306e\u3084\u308a\u65b9\u3067\u5354\u529b\u3059\u308b\u304b\u3069\u3046\u304b\u3092\u30e2\u30c7\u30eb\u5316\u3059\u308b\u3002\u751f\u7269\u5b66[\u7de8\u96c6]\u540c\u3058\u304f\u3001\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u751f\u7269\u5b66\u304a\u3088\u3073\u4fdd\u5168\u306e\u53d6\u308a\u7d44\u307f\u306b\u304a\u3044\u3066\u6709\u7528\u3067\u3042\u308b\u3002\u3053\u3053\u3067\u306f\u3001\u9802\u70b9\u304c\u7279\u5b9a\u306e\u7a2e\u304c\u5b58\u5728\uff08\u307e\u305f\u306f\u751f\u606f\uff09\u3059\u308b\u5730\u57df\u3092\u8868\u308f\u3059\u3053\u3068\u304c\u3067\u304d\u3001\u8fba\u306f\u5730\u57df\u9593\u306e\u79fb\u52d5\u7d4c\u8def\u307e\u305f\u306f\u79fb\u52d5\u3092\u8868\u308f\u3059\u3002\u3053\u306e\u60c5\u5831\u306f\u3001\u7e41\u6b96\u30d1\u30bf\u30fc\u30f3\u3092\u898b\u308b\u6642\u3084\u3001\u75c5\u6c17\u3084\u5bc4\u751f\u866b\u306e\u5e83\u304c\u308a\u3001\u79fb\u52d5\u304c\u4ed6\u306e\u7a2e\u306b\u3069\u306e\u3088\u3046\u306b\u5f71\u97ff\u3057\u3046\u308b\u304b\u3092\u8ffd\u8de1\u3059\u308b\u305f\u3081\u306b\u91cd\u8981\u3067\u3042\u308b\u3002\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u30b3\u30cd\u30af\u30c8\u30df\u30af\u30b9\u3067\u3082\u4f7f\u308f\u308c\u308b[30]\u3002\u795e\u7d4c\u7cfb\u306f\u30b0\u30e9\u30d5\u3068\u3057\u3066\u898b\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u3053\u3053\u3067\u3001\u7bc0\u70b9\u306f\u30cb\u30e5\u30fc\u30ed\u30f3\u3067\u3042\u308a\u3001\u8fba\u306f\u30cb\u30e5\u30fc\u30ed\u30f3\u9593\u306e\u3064\u306a\u304c\u308a\u3067\u3042\u308b\u3002\u6570\u5b66[\u7de8\u96c6]\u6570\u5b66\u3067\u306f\u3001\u30b0\u30e9\u30d5\u306f\u5e7e\u4f55\u5b66\u306a\u3089\u3073\u306b\u7d50\u3073\u76ee\u7406\u8ad6\u3068\u3044\u3063\u305f\u30c8\u30dd\u30ed\u30b8\u30fc\u306e\u7279\u5b9a\u306e\u5206\u91ce\u306b\u304a\u3044\u3066\u6709\u7528\u3067\u3042\u308b\u3002\u4ee3\u6570\u7684\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u7fa4\u8ad6\u3068\u5bc6\u63a5\u306a\u3064\u306a\u304c\u308a\u3092\u6301\u3064\u3002\u4ee3\u6570\u7684\u30b0\u30e9\u30d5\u7406\u8ad6\u306f\u52d5\u7684\u7cfb\u3084\u8907\u96d1\u6027\u3092\u542b\u3080\u591a\u304f\u306e\u5206\u91ce\u306b\u5fdc\u7528\u3055\u308c\u3066\u3044\u308b\u3002\u305d\u306e\u4ed6[\u7de8\u96c6]\u30b0\u30e9\u30d5\u69cb\u9020\u306f\u3001\u30b0\u30e9\u30d5\u306e\u305d\u308c\u305e\u308c\u306e\u8fba\u306b\u91cd\u307f\u3092\u5272\u308a\u5f53\u3066\u308b\u3053\u3068\u306b\u3088\u3063\u3066\u62e1\u5f35\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5\u306f\u3001\u5bfe\u3054\u3068\u306e\u3064\u306a\u304c\u308a\u304c\u4f55\u3089\u304b\u306e\u6570\u5024\u3092\u6301\u3064\u69cb\u9020\u3092\u8868\u308f\u3059\u305f\u3081\u306b\u4f7f\u308f\u308c\u308b\u3002\u4f8b\u3048\u3070\u3001\u30b0\u30e9\u30d5\u304c\u9053\u8def\u7db2\u3092\u8868\u308f\u3059\u3068\u3059\u308b\u3068\u3001\u91cd\u307f\u306f\u5404\u9053\u8def\u306e\u9577\u3055\u3092\u8868\u308f\u3059\u3053\u3068\u304c\u3067\u304d\u308b\u3060\u308d\u3046\u3002\u305d\u308c\u305e\u308c\u306e\u8fba\u306b\u95a2\u9023\u3057\u305f\u8907\u6570\u306e\u91cd\u307f\uff08\u8ddd\u96e2\u3001\u65c5\u884c\u6642\u9593\u3001\u91d1\u92ad\u7684\u30b3\u30b9\u30c8\u306a\u3069\uff09\u304c\u5b58\u5728\u3059\u308b\u304b\u3082\u3057\u308c\u306a\u3044\u3002\u3053\u306e\u3088\u3046\u306a\u91cd\u307f\u4ed8\u304d\u30b0\u30e9\u30d5\u306fGPS\u304a\u3088\u3073\u98db\u884c\u6642\u9593\u3068\u8cbb\u7528\u3092\u6bd4\u8f03\u3059\u308b\u65c5\u884c\u8a08\u753b\u63a2\u7d22\u30a8\u30f3\u30b8\u30f3\u3092\u30d7\u30ed\u30b0\u30e9\u30e0\u3059\u308b\u305f\u3081\u306b\u4e00\u822c\u7684\u306b\u4f7f\u308f\u308c\u308b\u3002\u554f\u984c\u3068\u5b9a\u7406[\u7de8\u96c6]2022\u5e74\u304b\u3089\u65e5\u672c\u3067\u5c0e\u5165\u3055\u308c\u308b\u9ad8\u7b49\u5b66\u6821\u65b0\u5b66\u7fd2\u6307\u5c0e\u8981\u9818\u306e\u6570\u5b66C\uff08\u516c\u5f0f\u914d\u5e03\u3055\u308c\u308b\u306e\u306f2024\u5e744\u6708\uff09\u306b\u306f\u300c\u56f3\u3001\u8868\u3001\u7d71\u8a08\u30b0\u30e9\u30d5\u3001\u96e2\u6563\u30b0\u30e9\u30d5\u53ca\u3073\u884c\u5217\u306a\u3069\u3092\u7528\u3044\u3066\u3001\u65e5\u5e38\u306e\u4e8b\u8c61\u3084\u793e\u4f1a\u306e\u4e8b\u8c61\u306a\u3069\u3092\u6570\u5b66\u7684\u306b\u8868\u73fe\u3057\u3001\u8003\u5bdf\u3059\u308b\u3053\u3068\u300d\u3068\u3042\u308a\u3001\u65e5\u672c\u3067\u306f\u521d\u3081\u3066\u30b0\u30e9\u30d5\u7406\u8ad6\u306b\u304b\u304b\u308f\u308b\u5206\u91ce\u304c\u9ad8\u7b49\u5b66\u6821\u306e\u6570\u5b66\u6559\u79d1\u66f8\u306b\u63b2\u8f09\u3055\u308c\u308b\u4e88\u5b9a\u3067\u3042\u308b[32]\u3002\u51fa\u5178\u3068\u88dc\u8db3[\u7de8\u96c6]^ \u6982\u5ff5^ \u30cf\u30a4\u30d1\u30fc\u30ea\u30f3\u30af^  (\u30e9\u30c6\u30f3\u8a9e) Leonhard Euler &#8211; Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128\u2013140.\u3000Konigsberg Bridge problem\u3092\u53c2\u7167\u3002^ Diestel,  p. 20^ \u30b0\u30e9\u30d5\u7406\u8ad6\u306e\u6b74\u53f2\u3092\u6271\u3063\u3066\u3044\u308bBiggs et al. (1998)\u306b\u30aa\u30a4\u30e9\u30fc\u306e\u8ad6\u6587\u306e\u82f1\u8a33\u3092\u542b\u3080\u7bc0\u304c\u3042\u308b\u3002^ \u8a73\u3057\u304f\u306f\u3001\u4e00\u7b46\u66f8\u304d\u306e\u9805\u3092\u53c2\u7167\u3002^ \u7121\u5411\u30b0\u30e9\u30d5\u3068\u6709\u5411\u30b0\u30e9\u30d5^ a b c d \u30c7\u30a3\u30fc\u30b9\u30c6\u30eb 2000, 1.1 \u30b0\u30e9\u30d5^ \u591a\u91cd\u30b0\u30e9\u30d5^ \u30d9\u30eb\u30b8\u30e5\u300c\u30b0\u30e9\u30d5\u306e\u7406\u8ad6I\u300dp.8.^ \u30c7\u30a3\u30fc\u30b9\u30c6\u30eb, 2000^ \u8328\u6728\u300c\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u30c7\u30fc\u30bf\u69cb\u9020\u300d^ \u9589\u8def^ Diestel, p. 115^ Hale, Scott A. (2013). \u201cMultilinguals and Wikipedia Editing\u201d. Proceedings of the 2014 ACM Conference on Web Science &#8211; WebSci &#8217;14:  99\u2013108. arXiv:1312.0976. doi:10.1145\/2615569.2615684. ISBN\u00a09781450326223.\u00a0^ Mashaghi, A. (2004). \u201cInvestigation of a protein complex network\u201d. European Physical Journal B 41 (1):  113\u2013121. arXiv:cond-mat\/0304207. Bibcode:\u00a02004EPJB&#8230;41..113M. doi:10.1140\/epjb\/e2004-00301-0.\u00a0^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M et al. (2019-07-01). \u201cCharacterizing the role of the structural connectome in seizure dynamics\u201d (\u82f1\u8a9e). Brain 142 (7):  1955\u20131972. doi:10.1093\/brain\/awz125. ISSN\u00a00006-8950. https:\/\/academic.oup.com\/brain\/article\/142\/7\/1955\/5491072.\u00a0^ Grandjean, Martin (2016). \u201cA social network analysis of Twitter: Mapping the digital humanities community\u201d. Cogent Arts &#038; Humanities 3 (1):  1171458. doi:10.1080\/23311983.2016.1171458.\u00a0^ Vecchio, F (2017). \u201c&#8221;Small World&#8221; architecture in brain connectivity and hippocampal volume in Alzheimer&#8217;s disease: a study via graph theory from EEG data\u201d. Brain Imaging and Behavior 11 (2):  473\u2013485. doi:10.1007\/s11682-016-9528-3. PMID\u00a026960946.\u00a0^ Vecchio, F (2013). \u201cBrain network connectivity assessed using graph theory in frontotemporal dementia\u201d. Neurology 81 (2):  134\u2013143. doi:10.1212\/WNL.0b013e31829a33f8.\u00a0^ \u201cTextGraphs: Graph-based Algorithms for Natural Language Processing\u201d. 2019\u5e747\u670826\u65e5\u95b2\u89a7\u3002^ Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields. New York: McGraw-Hill. p.\u00a0viii\u00a0^ Kumar, Ankush; Kulkarni, G. U. (2016-01-04). \u201cEvaluating conducting network based transparent electrodes from geometrical considerations\u201d. Journal of Applied Physics 119 (1):  015102. Bibcode:\u00a02016JAP&#8230;119a5102K. doi:10.1063\/1.4939280. ISSN\u00a00021-8979.\u00a0^ Grandjean, Martin (2015). &#8220;Social network analysis and visualization: Moreno\u2019s Sociograms revisited&#8221;. Redesigned network strictly based on Moreno (1934), Who Shall Survive.^ Rosen, Kenneth H. (2011-06-14). Discrete mathematics and its applications (7th ed.). New York: McGraw-Hill. ISBN\u00a0978-0-07-338309-5\u00a0^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M et al. (2019-07-01). \u201cCharacterizing the role of the structural connectome in seizure dynamics\u201d (\u82f1\u8a9e). Brain 142 (7):  1955\u20131972. doi:10.1093\/brain\/awz125. ISSN\u00a00006-8950. https:\/\/academic.oup.com\/brain\/article\/142\/7\/1955\/5491072.\u00a0^ Fritsch (2012), p. 99^ \u201c\u9ad8\u6821\u300c\u65b0\u5b66\u7fd2\u6307\u5c0e\u8981\u9818\u300d\u306f\u6559\u3048\u65b9\u6539\u9769 &#8211; \u65fa\u6587\u793e \u6559\u80b2\u60c5\u5831\u30bb\u30f3\u30bf\u30fc\u201d.   eic.obunsha.co.jp. 2019\u5e742\u67081\u65e5\u95b2\u89a7\u3002\u53c2\u8003\u6587\u732e[\u7de8\u96c6]\u30d9\u30eb\u30b8\u30e5, C.\u300e\u30b0\u30e9\u30d5\u306e\u7406\u8ad6I\u300f\u4f0a\u7406\u6b63\u592b\u30fb\u4f0a\u7406\u7531\u7f8e\u30fb\u5ca9\u576a\u79c0\u4e00\u30fb\u5c0f\u6797\u6b23\u543e\u30fb\u4f50\u85e4\u5275\u30fb\u661f\u5b88\u8a33\u3001\u30b5\u30a4\u30a8\u30f3\u30b9\u793e\u30011976\u5e74\u3002ISBN\u00a04-7819-0111-5\u3002\u30c7\u30a3\u30fc\u30b9\u30c6\u30eb, \u30e9\u30a4\u30f3\u30cf\u30eb\u30c8\u300e\u30b0\u30e9\u30d5\u7406\u8ad6\u300f\u6839\u4e0a\u751f\u4e5f\u30fb\u592a\u7530\u514b\u5f18\u8a33\u3001\u30b7\u30e5\u30d7\u30ea\u30f3\u30ac\u30fc\u30fb\u30d5\u30a7\u30a2\u30e9\u30fc\u30af\u6771\u4eac\u30012000\u5e74\u3001\u539f\u66f8\u7b2c2\u7248\u3002ISBN\u00a0978-4-431-70876-6\u3002(\u73fe\u5728\u306f\u4e38\u5584\u306b\u79fb\u7ba1)Reinhard Diestel (2010), Graphentheorie. Springer-Verlag, Vierte Auflage, 2010 Korrigierter Nachdruck 2012 Heidelberg xviii+355 Seiten, 129 Abbildungen September 2010 (2006, 2000, 1996) ISBN 978-3-642-14911-5 EUR 32,99.Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. (1998). Graph theory 1736\u20131936 (Reprint with corrections ed.). Oxford University Press. ISBN\u00a00-19-853916-9. MR0879117. Zbl\u00a00904.05001. https:\/\/books.google.com\/books?id=XqYTk0sXmpoC\u00a0Bondy, J. A.; Murty, U. S. R. (2008). Graph theory. Graduate Texts in Mathematics. 244. Springer. ISBN\u00a0978-1-84628-969-9. MR2368647\u00a0Rudolf Fritsch, Gerda Fritsch, translated by J.lie Peschke:The Four-Color Theorem (2012): History, Topological Foundations, and Idea of Proof, Springer; Softcover reprint of the original 1st edition 1998; ISBN 978-1-46127-254-0\u95a2\u9023\u6587\u732e[\u7de8\u96c6]\u65e5\u672c\u8a9e\u306e\u6587\u732e[\u7de8\u96c6]\u6839\u4e0a\u751f\u4e5f\u300e\u96e2\u6563\u69cb\u9020\u300f\u5171\u7acb\u51fa\u7248\u3008\u60c5\u5831\u6570\u5b66\u8b1b\u5ea7 3\u3009\u30011993\u5e74\u3002ISBN\u00a04-320-02653-5\u3002\u79cb\u5c71\u4ec1\u3001\u30ed\u30ca\u30eb\u30c9\u30fb\u30eb\u30a4\u30b9\u30fb\u30b0\u30e9\u30cf\u30e0\u300e\u96e2\u6563\u6570\u5b66\u5165\u9580\u300f\u671d\u5009\u66f8\u5e97\u3008\u5165\u9580\u6709\u9650\u30fb\u96e2\u6563\u306e\u6570\u5b66 1\u3009\u30011993\u5e74\u3002ISBN\u00a04-254-11419-2\u3002\u79cb\u5c71\u4ec1 \u300e\u30b0\u30e9\u30d5\u7406\u8ad6\u6700\u524d\u7dda\u300f\u671d\u5009\u66f8\u5e97 ISBN 978-4-254-11420-1.\u52a0\u7d0d\u5e79\u96c4 \u300e\u60c5\u5831\u79d1\u5b66\u306e\u305f\u3081\u306e\u30b0\u30e9\u30d5\u7406\u8ad6\u300f\u671d\u5009\u66f8\u5e97 ISBN 978-4-254-11424-9.\u30cf\u30e9\u30ea\u30fc, \u30d5\u30e9\u30f3\u30af\u300e\u30b0\u30e9\u30d5\u7406\u8ad6\u300f\u6c60\u7530\u8c9e\u96c4\u8a33\u3001\u5171\u7acb\u51fa\u7248\u30011971\u5e74\u3002ISBN\u00a0978-4-320-01073-4\u3002\u8328\u6728\u4fca\u79c0\u300e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u30c7\u30fc\u30bf\u69cb\u9020\u300f\u662d\u6643\u5802\u30011986\u5e74\u3002ISBN\u00a04-7856-0119-1\u3002\u9234\u6728\u664b\u4e00\u7de8\u8457 \u300e\u6570\u5b66\u6559\u6750\u3068\u3057\u3066\u306e\u30b0\u30e9\u30d5\u7406\u8ad6\u300f, \u65e9\u7a32\u7530\u6559\u80b2\u53e2\u66f8 31, \u5b66\u6587\u793e, ISBN 978-4-76202-253-1\u30ce\u30e9\u30fb\u30cf\u30fc\u30c4\u30d5\u30a3\u30fc\u30eb\u30c9&#038;\u30b2\u30fc\u30cf\u30fc\u30c9\u30fb\u30ea\u30f3\u30b2\u30eb\u8457 \u9234\u6728\u664b\u4e00\u8a33,\u300e\u30b0\u30e9\u30d5\u7406\u8ad6\u5165\u9580\u300f,\u30b5\u30a4\u30a8\u30f3\u30b9\u793e, ISBN 978-4-78190-654-6\u30dc\u30ed\u30d0\u30b7\u30e5\u30fb\u30d9\u30fc\u30e9\u8457 \u658e\u85e4\u4f38\u81ea, \u897f\u95a2\u9686\u592b\u8a33,\u300e\u30b0\u30e9\u30d5\u7406\u8ad6\u5165\u9580\u300f,\u57f9\u98a8\u9928, ISBN 978-4-56300-544-3\u65e5\u672c\u8a9e\u4ee5\u5916[\u7de8\u96c6]Berge, Claude (1958), Th\u00e9orie des graphes et ses applications, Collection Universitaire de Math\u00e9matiques II, Paris: Dunod. English edition, Wiley 1961; Methuen &#038; Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.ISBN 978-0-48641-975-6.Chartrand, Gary (1985), Introductory Graph Theory, Dover, ISBN 0-486-24775-9.Leonhard Euler, Euler Complete Edition (Opera Omnia: Series 1, Volume 7, pp. 1 &#8211; 10)Hajnal P\u00e9ter (2003), Gr\u00e1felm\u00e9let &#8211; Polygon jegyzetHarary, Frank (1969), Graph Theory, Reading, MA: Addison-Wesley.Harary, Frank; Palmer, Edgar M. (1973), Graphical Enumeration, New York, NY: Academic Press.Lov\u00e1sz L\u00e1szl\u00f3 (2008), Kombinatorikai probl\u00e9m\u00e1k \u00e9s feladatok, Typotex Kiad\u00f3, ISBN 978-963-9664-93-7.Manfred Nitzsche (2004), Graphen f\u00fcr Einsteiger, Rund um das Haus vom Nikolaus. XII, 233 S. Br. \u20ac 22,90 ISBN 3-528-03215-4Peter Gritzmann, Ren\u00e9 Brandenberg (2003) Das Geheimnis des k\u00fcrzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin &#8211; Heidelberg (2.Aufl.). ISBN 3-540-00045-3William Thomas Tutte (2001), Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3.\u95a2\u9023\u9805\u76ee[\u7de8\u96c6]\u30a6\u30a3\u30ad\u30d6\u30c3\u30af\u30b9\u306b\u30b0\u30e9\u30d5\u7406\u8ad6\u95a2\u9023\u306e\u89e3\u8aac\u66f8\u30fb\u6559\u79d1\u66f8\u304c\u3042\u308a\u307e\u3059\u3002\u5916\u90e8\u30ea\u30f3\u30af[\u7de8\u96c6]"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki10\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki10\/archives\/114947#breadcrumbitem","name":"\u30b0\u30e9\u30d5\u7406\u8ad6 &#8211; Wikipedia"}}]}]