グラフ理論 - Wikibooks

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available" lang="ja" dir="ltr"> <head> <meta charset="UTF-8"> <title>グラフ理論 - Wikibooks</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )jawikibooksmwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat": "ja","wgMonthNames":["","1月","2月","3月","4月","5月","6月","7月","8月","9月","10月","11月","12月"],"wgRequestId":"5357c6eb-bda4-461a-bee3-392707078940","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"グラフ理論","wgTitle":"グラフ理論","wgCurRevisionId":248294,"wgRevisionId":248294,"wgArticleId":16744,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["数学","離散グラフ"],"wgPageViewLanguage":"ja","wgPageContentLanguage":"ja","wgPageContentModel":"wikitext","wgRelevantPageName":"グラフ理論","wgRelevantArticleId":16744,"wgTempUserName":null,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikibooks","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgVisualEditor":{"pageLanguageCode":"ja","pageLanguageDir": "ltr","pageVariantFallbacks":"ja"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":7000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q131476","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"wgSiteNoticeId":"2.8"};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","mediawiki.page.gallery.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready", "ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready","ext.dismissableSiteNotice.styles":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","wikibase.client.vector-2022","ext.checkUser.clientHints","wikibase.sidebar.tracking","ext.dismissableSiteNotice"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=ja&modules=ext.dismissableSiteNotice.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cmediawiki.page.gallery.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=ja&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=ja&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="グラフ理論 - Wikibooks"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//ja.m.wikibooks.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96"> <link rel="alternate" type="application/x-wiki" title="編集" href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit"> <link rel="icon" href="/static/favicon/wikibooks.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikibooks (ja)"> <link rel="EditURI" type="application/rsd+xml" href="//ja.wikibooks.org/w/api.php?action=rsd"> <link rel="canonical" href="https://ja.wikibooks.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ja"> <link rel="alternate" type="application/atom+xml" title="WikibooksのAtomフィード" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E6%9C%80%E8%BF%91%E3%81%AE%E6%9B%B4%E6%96%B0&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-グラフ理論 rootpage-グラフ理論 skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">コンテンツにスキップ</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="サイト"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="メインメニュー" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">メインメニュー</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">メインメニュー</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">非表示</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> ナビゲーション </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8" title="メインページに移動する [z]" accesskey="z"><span>メインページ</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikibooks:%E3%82%B3%E3%83%9F%E3%83%A5%E3%83%8B%E3%83%86%E3%82%A3%E3%83%BB%E3%83%9D%E3%83%BC%E3%82%BF%E3%83%AB" title="このプロジェクトについて、できること、情報を入手する場所"><span>コミュニティ・ポータル</span></a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikibooks:%E8%AB%87%E8%A9%B1%E5%AE%A4"><span>談話室</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E6%9C%80%E8%BF%91%E3%81%AE%E6%9B%B4%E6%96%B0" title="このウィキにおける最近の更新の一覧 [r]" accesskey="r"><span>最近の更新</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%81%8A%E3%81%BE%E3%81%8B%E3%81%9B%E8%A1%A8%E7%A4%BA" title="無作為に選択されたページを読み込む [x]" accesskey="x"><span>おまかせ表示</span></a></li><li id="n-commonsupload" class="mw-list-item"><a href="http://commons.wikimedia.org/wiki/Special:UploadWizard?uselang=ja" title="画像などのメディアファイルをウィキメディア・コモンズへアップロード"><span>アップロード（ウィキメディア・コモンズ）</span></a></li> </ul> </div> </div> <div id="p-help" class="vector-menu mw-portlet mw-portlet-help" > <div class="vector-menu-heading"> ヘルプ </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/%E3%83%98%E3%83%AB%E3%83%97:%E7%9B%AE%E6%AC%A1" title="情報を得る場所"><span>ヘルプ</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikibooks.svg" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikibooks" src="/static/images/mobile/copyright/wikibooks-wordmark-vi.svg" style="width: 7.5em; height: 0.9375em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/%E7%89%B9%E5%88%A5:%E6%A4%9C%E7%B4%A2" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Wikibooks内を検索 [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>検索</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Wikibooks内を検索" aria-label="Wikibooks内を検索" autocapitalize="sentences" title="Wikibooks内を検索 [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="特別:検索"> </div> <button class="cdx-button cdx-search-input__end-button">検索</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="個人用ツール"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="表示"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="ページのフォントサイズ、幅、色の外観を変更する" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="表示" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">表示</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ja.wikibooks.org&uselang=ja" class=""><span>寄付</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%82%A2%E3%82%AB%E3%82%A6%E3%83%B3%E3%83%88%E4%BD%9C%E6%88%90&returnto=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="アカウントを作成してログインすることをお勧めしますが、必須ではありません" class=""><span>アカウント作成</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%AD%E3%82%B0%E3%82%A4%E3%83%B3&returnto=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="ログインすることを推奨します。ただし、必須ではありません。 [o]" accesskey="o" class=""><span>ログイン</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out user-links-collapsible-item" title="その他の操作" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="個人用ツール" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">個人用ツール</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="利用者メニュー" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_ja.wikibooks.org&uselang=ja"><span>寄付</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%82%A2%E3%82%AB%E3%82%A6%E3%83%B3%E3%83%88%E4%BD%9C%E6%88%90&returnto=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="アカウントを作成してログインすることをお勧めしますが、必須ではありません"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>アカウント作成</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%AD%E3%82%B0%E3%82%A4%E3%83%B3&returnto=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="ログインすることを推奨します。ただし、必須ではありません。 [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>ログイン</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"><div id="mw-dismissablenotice-anonplace"></div><script>(function(){var node=document.getElementById("mw-dismissablenotice-anonplace");if(node){node.outerHTML="\u003Cdiv class=\"mw-dismissable-notice\"\u003E\u003Cdiv class=\"mw-dismissable-notice-close\"\u003E[\u003Ca tabindex=\"0\" role=\"button\"\u003E非表示\u003C/a\u003E]\u003C/div\u003E\u003Cdiv class=\"mw-dismissable-notice-body\"\u003E\u003C!-- CentralNotice --\u003E\u003Cdiv id=\"localNotice\" data-nosnippet=\"\"\u003E\u003Cdiv class=\"anonnotice\" lang=\"ja\" dir=\"ltr\"\u003E\u003Cp style=\"text-align:center\"\u003E継続した参加を行う場合は\u003Ca href=\"/wiki/%E7%89%B9%E5%88%A5:%E3%83%AD%E3%82%B0%E3%82%A4%E3%83%B3\" title=\"特別:ログイン\"\u003Eログイン\u003C/a\u003Eをご一考ください\u003C/p\u003E\u003C/div\u003E\u003C/div\u003E\u003C/div\u003E\u003C/div\u003E";}}());</script></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="サイト"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="目次" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">目次</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">非表示</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">ページ先頭</div> </a> </li> <li id="toc-グラフとは" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#グラフとは"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>グラフとは</span> </div> </a> <button aria-controls="toc-グラフとは-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>グラフとはサブセクションを切り替えます</span> </button> <ul id="toc-グラフとは-sublist" class="vector-toc-list"> <li id="toc-グラフの表記" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#グラフの表記"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>グラフの表記</span> </div> </a> <ul id="toc-グラフの表記-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-グラフの作図" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#グラフの作図"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>グラフの作図</span> </div> </a> <ul id="toc-グラフの作図-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-例題1" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#例題1"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>例題1</span> </div> </a> <ul id="toc-例題1-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-問題1" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#問題1"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.4</span> <span>問題1</span> </div> </a> <ul id="toc-問題1-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-位数とサイズ" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#位数とサイズ"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>位数とサイズ</span> </div> </a> <ul id="toc-位数とサイズ-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-次数" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#次数"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>次数</span> </div> </a> <ul id="toc-次数-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-道と閉路" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#道と閉路"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>道と閉路</span> </div> </a> <ul id="toc-道と閉路-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-同型のグラフ" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#同型のグラフ"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>同型のグラフ</span> </div> </a> <ul id="toc-同型のグラフ-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-連結なグラフ" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#連結なグラフ"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>連結なグラフ</span> </div> </a> <ul id="toc-連結なグラフ-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-完全グラフ" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#完全グラフ"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>完全グラフ</span> </div> </a> <ul id="toc-完全グラフ-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-特殊なグラフとその構成" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#特殊なグラフとその構成"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>特殊なグラフとその構成</span> </div> </a> <ul id="toc-特殊なグラフとその構成-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-木" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#木"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>木</span> </div> </a> <button aria-controls="toc-木-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>木サブセクションを切り替えます</span> </button> <ul id="toc-木-sublist" class="vector-toc-list"> <li id="toc-順序木" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#順序木"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.1</span> <span>順序木</span> </div> </a> <ul id="toc-順序木-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-問題の解答" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#問題の解答"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>問題の解答</span> </div> </a> <button aria-controls="toc-問題の解答-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>問題の解答サブセクションを切り替えます</span> </button> <ul id="toc-問題の解答-sublist" class="vector-toc-list"> <li id="toc-問題1_2" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#問題1_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">10.1</span> <span>問題1</span> </div> </a> <ul id="toc-問題1_2-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-ファイルのダウンロード" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#ファイルのダウンロード"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>ファイルのダウンロード</span> </div> </a> <ul id="toc-ファイルのダウンロード-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="目次" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="目次の表示・非表示を切り替え" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">目次の表示・非表示を切り替え</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">グラフ理論</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="特定の記事の別の言語版に移動します。利用可能な言語2件" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-2" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">2の言語版</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikibooks.org/wiki/Graph_Theory" title="英語: Graph Theory" lang="en" hreflang="en" data-title="Graph Theory" data-language-autonym="English" data-language-local-name="英語" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikibooks.org/wiki/Teor%C3%ADa_de_grafos" title="スペイン語: Teoría de grafos" lang="es" hreflang="es" data-title="Teoría de grafos" data-language-autonym="Español" data-language-local-name="スペイン語" class="interlanguage-link-target"><span>Español</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q131476#sitelinks-wikibooks" title="言語間リンクを編集" class="wbc-editpage">リンクを編集</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="名前空間"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="本文を閲覧 [c]" accesskey="c"><span>本文</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/%E3%83%88%E3%83%BC%E3%82%AF:%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" rel="discussion" title="本文ページについての議論 [t]" accesskey="t"><span>議論</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="別の言語に切り替える" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">日本語</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="表示"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96"><span>閲覧</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit" title="このページを編集 [e]" accesskey="e"><span>編集</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=history" title="このページの過去の版 [h]" accesskey="h"><span>履歴表示</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="ページツール"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="ツールボックス" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">ツールボックス</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">ツール</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">非表示</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="その他の操作" > <div class="vector-menu-heading"> 操作 </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96"><span>閲覧</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit" title="このページを編集 [e]" accesskey="e"><span>編集</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=history"><span>履歴表示</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> 全般 </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%83%AA%E3%83%B3%E3%82%AF%E5%85%83/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" title="ここにリンクしている全ウィキページの一覧 [j]" accesskey="j"><span>リンク元</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E9%96%A2%E9%80%A3%E3%83%9A%E3%83%BC%E3%82%B8%E3%81%AE%E6%9B%B4%E6%96%B0%E7%8A%B6%E6%B3%81/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" rel="nofollow" title="このページからリンクしているページの最近の更新 [k]" accesskey="k"><span>関連ページの更新状況</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/%E7%89%B9%E5%88%A5:%E7%89%B9%E5%88%A5%E3%83%9A%E3%83%BC%E3%82%B8%E4%B8%80%E8%A6%A7" title="特別ページの一覧 [q]" accesskey="q"><span>特別ページ</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&oldid=248294" title="このページのこの版への固定リンク"><span>この版への固定リンク</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=info" title="このページについての詳細情報"><span>ページ情報</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%81%93%E3%81%AE%E3%83%9A%E3%83%BC%E3%82%B8%E3%82%92%E5%BC%95%E7%94%A8&page=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&id=248294&wpFormIdentifier=titleform" title="このページの引用方法"><span>このページを引用</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:UrlShortener&url=https%3A%2F%2Fja.wikibooks.org%2Fwiki%2F%25E3%2582%25B0%25E3%2583%25A9%25E3%2583%2595%25E7%2590%2586%25E8%25AB%2596"><span>短縮URLを取得する</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:QrCode&url=https%3A%2F%2Fja.wikibooks.org%2Fwiki%2F%25E3%2582%25B0%25E3%2583%25A9%25E3%2583%2595%25E7%2590%2586%25E8%25AB%2596"><span>QRコードをダウンロード</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> 印刷/書き出し </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:%E3%83%96%E3%83%83%E3%82%AF&bookcmd=book_creator&referer=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96"><span>ブックの新規作成</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=%E7%89%B9%E5%88%A5:DownloadAsPdf&page=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=show-download-screen"><span>PDF 形式でダウンロード</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&printable=yes" title="このページの印刷用ページ [p]" accesskey="p"><span>印刷用バージョン</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> 他のプロジェクト </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Graph_theory" hreflang="en"><span>コモンズ</span></a></li><li class="wb-otherproject-link wb-otherproject-wikipedia mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96" hreflang="ja"><span>ウィキペディア</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q131476" title="関連付けられたデータリポジトリ項目へのリンク [g]" accesskey="g"><span>ウィキデータ項目</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="ページツール"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="表示"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">表示</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">サイドバーに移動</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">非表示</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">出典: フリー教科書『ウィキブックス（Wikibooks）』</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="ja" dir="ltr"><style data-mw-deduplicate="TemplateStyles:r252148">.mw-parser-output .pathnavbox{clear:both;border:1px outset #eef;padding:0.3em 0.6em;margin:0 0 0.5em 0;background-color:inherit;font-size:90%}.mw-parser-output .pathnavbox ul{list-style:none none;margin-top:0;margin-bottom:0}.mw-parser-output .pathnavbox>ul{margin:0}.mw-parser-output .pathnavbox ul li{margin:0}</style><div class="pathnavbox"><a href="/wiki/%E6%95%B0%E5%AD%A6" title="数学">数学</a> > <b>グラフ理論</b></div> <p>　グラフ理論（Graph theory）とは、グラフの持つ様々な性質を解明し、日常の様々な場面で利用することを目的とする数学分野の1つである。 </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="グラフとは"><span id=".E3.82.B0.E3.83.A9.E3.83.95.E3.81.A8.E3.81.AF"></span>グラフとは</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=1" title="節を編集: グラフとは"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　グラフ理論における<b>グラフ</b> （Graph）とは、<b>頂点</b>(node)と<b>辺</b>(edge)により構成された図形のことである。グラフは主に、<b>有向グラフ</b> （directed graph）と<b>無向グラフ</b> （undirected graph）の2つに分類される。有向グラフとは、頂点と向きを持つ辺（矢印）により構成されたグラフであり、無向グラフとは、頂点と辺により構成されたグラフである。有向グラフの辺を有向辺、無向グラフの辺を無向辺という。また、ある2頂点が辺で結ばれている場合、その2頂点は隣接するという。この教科書では、特に利用分野の多い無向グラフについて説明する。そのため、この教科書では、無向グラフを単にグラフと記述することとする。 </p> <div class="mw-heading mw-heading3"><h3 id="グラフの表記"><span id=".E3.82.B0.E3.83.A9.E3.83.95.E3.81.AE.E8.A1.A8.E8.A8.98"></span>グラフの表記</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=2" title="節を編集: グラフの表記"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　グラフは頂点の集合と辺の集合の2つの順序対で構成される。グラフ<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5f3c8921a3b352de45446a6789b104458c9f90b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}"></span>を構成する頂点の集合を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af0f6064540e84211d0ffe4dac72098adfa52845" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}"></span>、辺の集合を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}"></span>とし、<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}"></span>と表記する。頂点を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span>や<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span>で表すことが多く、頂点<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mo>,</mo> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u,v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e66f4b32a0181923cc1337a5634f38241e5c697" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.491ex; height:2.009ex;" alt="{\displaystyle u,v}"></span>を結ぶ辺を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{u,v\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{u,v\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f507af3d28091510daed6d4241af30d88c1c2c92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle \{u,v\}}"></span>または、<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle uv}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle uv}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e6b4c628431f1c0bdf17baf5b94d2f46caa4c5f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.457ex; height:1.676ex;" alt="{\displaystyle uv}"></span>と表す。しかし、紛らわしい表記であるため、この教科書では、<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{u,v\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{u,v\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f507af3d28091510daed6d4241af30d88c1c2c92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle \{u,v\}}"></span>と表記することとする。ただし、<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{u,v\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{u,v\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f507af3d28091510daed6d4241af30d88c1c2c92" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle \{u,v\}}"></span>と<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v,u\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>v</mi> <mo>,</mo> <mi>u</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{v,u\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b383f631e9014713dbeb4ec2a7ecbea89bc9fa07" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle \{v,u\}}"></span>はどちらでも構わない。 </p> <div class="mw-heading mw-heading3"><h3 id="グラフの作図"><span id=".E3.82.B0.E3.83.A9.E3.83.95.E3.81.AE.E4.BD.9C.E5.9B.B3"></span>グラフの作図</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=3" title="節を編集: グラフの作図"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　「グラフの定義」で説明したとおり、グラフは頂点と辺により構成される。とは言うものの、実際にどのように作図すればいいのかわからないだろう。この節では、グラフの作図について説明する。まず、頂点を丸で表し、辺を直線または、曲線で表す。そのとき、マルの大きさや直線の長さ、曲線の曲がり具合はグラフの本質には関係ないので、厳密に作図する必要はない。以下にグラフの作図例を紹介する。 </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 150px;"><span typeof="mw:File"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wikibooks_graph_theory.png" class="mw-file-description" title="作図例"><img alt="作図例" src="//upload.wikimedia.org/wikipedia/commons/thumb/5/50/Wikibooks_graph_theory.png/193px-Wikibooks_graph_theory.png" decoding="async" width="193" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/50/Wikibooks_graph_theory.png/289px-Wikibooks_graph_theory.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/50/Wikibooks_graph_theory.png/386px-Wikibooks_graph_theory.png 2x" data-file-width="448" data-file-height="279" /></a></span></div> <div class="gallerytext">作図例</div> </li> </ul> <p>頂点の周囲に<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}"></span>や<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span>などと記すと、グラフを表記するとき、便利である。頂点の中にラベル（重み）を記す場合があるが、まず、グラフの基本から説明する必要があるため、この節で紹介するのはやめておく。 </p> <div class="mw-heading mw-heading3"><h3 id="例題1"><span id=".E4.BE.8B.E9.A1.8C1"></span>例題1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=4" title="節を編集: 例題1"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>(1)　以下のグラフ<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}"></span>を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(V_{1},E_{1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{1}=(V_{1},E_{1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ce54faeead4cd211047907a335458e7dc8306daf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{1}=(V_{1},E_{1})}"></span>の形式で表せ。 </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 150px;"><span typeof="mw:File"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wikibooks_graph_theory2.png" class="mw-file-description" title="'"`UNIQ--postMath-00000011-QINU`"'"><img alt="'"`UNIQ--postMath-00000011-QINU`"'" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/15/Wikibooks_graph_theory2.png/124px-Wikibooks_graph_theory2.png" decoding="async" width="124" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/15/Wikibooks_graph_theory2.png/186px-Wikibooks_graph_theory2.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/15/Wikibooks_graph_theory2.png/248px-Wikibooks_graph_theory2.png 2x" data-file-width="288" data-file-height="279" /></a></span></div> <div class="gallerytext"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}"></span></div> </li> </ul> <p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7b02987e06ed85df762eee898b567bd11f7c4421" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.662ex; height:2.843ex;" alt="{\displaystyle V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{1}=\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E_{1}=\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57cbf3d1ea9a869dffdf6d9ec5dd6c0fcd930e72" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.185ex; height:2.843ex;" alt="{\displaystyle E_{1}=\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\}}"></span>であるから、<br /> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{1}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a89b1ab2ac65e64a2abdd18039a4eb542fdc1b22" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:59.294ex; height:2.843ex;" alt="{\displaystyle G_{1}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\}\})}"></span><br /><br /> (2)　グラフ<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{2}\},\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{3},v_{4}\}\})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{2}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{2}\},\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{3},v_{4}\}\})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e12d6d1ef52f6d8714fef7e729392cb097a748" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:68.05ex; height:2.843ex;" alt="{\displaystyle G_{2}=(\{v_{1},v_{2},v_{3},v_{4}\},\{\{v_{1},v_{2}\},\{v_{1},v_{3}\},\{v_{1},v_{4}\},\{v_{2},v_{3}\},\{v_{3},v_{4}\}\})}"></span>を作図せよ。 </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 150px;"><span typeof="mw:File"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wikibooks_graph_theory3.png" class="mw-file-description" title="'"`UNIQ--postMath-00000016-QINU`"'"><img alt="'"`UNIQ--postMath-00000016-QINU`"'" src="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Wikibooks_graph_theory3.png/124px-Wikibooks_graph_theory3.png" decoding="async" width="124" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/57/Wikibooks_graph_theory3.png/186px-Wikibooks_graph_theory3.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/57/Wikibooks_graph_theory3.png/248px-Wikibooks_graph_theory3.png 2x" data-file-width="288" data-file-height="279" /></a></span></div> <div class="gallerytext"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/645011b0c6933a02f5f7d84624f78220d747427e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}"></span></div> </li> </ul> <div class="mw-heading mw-heading3"><h3 id="問題1"><span id=".E5.95.8F.E9.A1.8C1"></span>問題1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=5" title="節を編集: 問題1"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>(1)　以下のグラフ<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d68b13104a6f81e902fca48f10a1531b3e592938" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}"></span>を<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}=(V_{3},E_{3})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>V</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{3}=(V_{3},E_{3})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/423b4281813a36cd40a95c3c3f2522dc7e02cde3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.002ex; height:2.843ex;" alt="{\displaystyle G_{3}=(V_{3},E_{3})}"></span>の形式で表せ。 </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 150px;"><span typeof="mw:File"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wikibooks_graph_theory4.png" class="mw-file-description" title="'"`UNIQ--postMath-00000019-QINU`"'"><img alt="'"`UNIQ--postMath-00000019-QINU`"'" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Wikibooks_graph_theory4.png/193px-Wikibooks_graph_theory4.png" decoding="async" width="193" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Wikibooks_graph_theory4.png/289px-Wikibooks_graph_theory4.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Wikibooks_graph_theory4.png/386px-Wikibooks_graph_theory4.png 2x" data-file-width="448" data-file-height="279" /></a></span></div> <div class="gallerytext"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d68b13104a6f81e902fca48f10a1531b3e592938" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{3}}"></span></div> </li> </ul> <p>(2)　グラフ<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{4}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{2},v_{3}\},\{v_{2},v_{5}\},\{v_{3},v_{4}\},\{v_{3},v_{5}\},\{v_{4},v_{5}\}\})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{4}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{2},v_{3}\},\{v_{2},v_{5}\},\{v_{3},v_{4}\},\{v_{3},v_{5}\},\{v_{4},v_{5}\}\})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b92cf20ce972e8bbf98b2b2426f79c4486833a1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:80.023ex; height:2.843ex;" alt="{\displaystyle G_{4}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{2},v_{3}\},\{v_{2},v_{5}\},\{v_{3},v_{4}\},\{v_{3},v_{5}\},\{v_{4},v_{5}\}\})}"></span>を作図せよ。 </p> <div class="mw-heading mw-heading2"><h2 id="位数とサイズ"><span id=".E4.BD.8D.E6.95.B0.E3.81.A8.E3.82.B5.E3.82.A4.E3.82.BA"></span>位数とサイズ</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=6" title="節を編集: 位数とサイズ"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　頂点の数を位数（order）、辺の数をサイズという。 </p> <div class="mw-heading mw-heading2"><h2 id="次数"><span id=".E6.AC.A1.E6.95.B0"></span>次数</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=7" title="節を編集: 次数"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　グラフにおける次数（degree）とは、ある頂点に結ばれている辺の数である。 </p> <div class="mw-heading mw-heading2"><h2 id="道と閉路"><span id=".E9.81.93.E3.81.A8.E9.96.89.E8.B7.AF"></span>道と閉路</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=8" title="節を編集: 道と閉路"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　あるグラフにおいて、<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{0},v_{1}\},\{v_{1},v_{2}\},\cdots ,\{v_{n-1},v_{n}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{v_{0},v_{1}\},\{v_{1},v_{2}\},\cdots ,\{v_{n-1},v_{n}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/207d04d81a044a6c0f31193a6f976f0d1e44d621" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.809ex; height:2.843ex;" alt="{\displaystyle \{v_{0},v_{1}\},\{v_{1},v_{2}\},\cdots ,\{v_{n-1},v_{n}\}}"></span>がすべて辺であるとき、それぞれの辺の集合を頂点<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/60faad24775635f4722ccc438093dbbfe05f34ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.182ex; height:2.009ex;" alt="{\displaystyle v_{0}}"></span> と頂点<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d5615ffa6233b0d09d5bafafb58a752c1e8de95f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.346ex; height:2.009ex;" alt="{\displaystyle v_{n}}"></span>を結ぶ<b>道</b>(path)と言う。 </p> <div class="mw-heading mw-heading2"><h2 id="同型のグラフ"><span id=".E5.90.8C.E5.9E.8B.E3.81.AE.E3.82.B0.E3.83.A9.E3.83.95"></span>同型のグラフ</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=9" title="節を編集: 同型のグラフ"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　ある2つのグラフが同型（isomorphism）であるということは、それぞれのグラフを構成する頂点と辺の結びつきが同じであるということである。 </p> <div class="mw-heading mw-heading2"><h2 id="連結なグラフ"><span id=".E9.80.A3.E7.B5.90.E3.81.AA.E3.82.B0.E3.83.A9.E3.83.95"></span>連結なグラフ</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=10" title="節を編集: 連結なグラフ"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　連結(connected)なグラフとは、任意の2頂点間に道が存在するグラフのことである。 </p> <div class="mw-heading mw-heading2"><h2 id="完全グラフ"><span id=".E5.AE.8C.E5.85.A8.E3.82.B0.E3.83.A9.E3.83.95"></span>完全グラフ</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=11" title="節を編集: 完全グラフ"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　完全グラフ（complete graph）とは、すべての頂点同士が辺で結ばれているグラフのことである。頂点数<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>の完全グラフを<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>K</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle K_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2b988ea630d2c5571afe47efa3d3b251708acb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.192ex; height:2.509ex;" alt="{\displaystyle K_{n}}"></span>と表す。 </p> <div class="mw-heading mw-heading2"><h2 id="特殊なグラフとその構成"><span id=".E7.89.B9.E6.AE.8A.E3.81.AA.E3.82.B0.E3.83.A9.E3.83.95.E3.81.A8.E3.81.9D.E3.81.AE.E6.A7.8B.E6.88.90"></span>特殊なグラフとその構成</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=12" title="節を編集: 特殊なグラフとその構成"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>オイラーグラフ：　オイラー閉トレイルが存在するグラフをオイラーグラフと呼ぶ。 </p><p>オイラー閉トレイル：　グラフのすべての辺とすべての点を含む閉トレイルをオイラー閉トレイルと呼ぶ。 </p><p>オイラートレイル：　グラフのすべての辺とすべての点を含むトレイルをオイラートレイルと呼ぶ。 </p><p>ハミルトングラフ：　ハミルトン閉路を含むグラフをハミルトングラフと呼ぶ。 </p><p>ハミルトン閉路：　グラフのすべての頂点を含む閉路をハミルトン閉路と呼ぶ。 </p> <div class="mw-heading mw-heading2"><h2 id="木"><span id=".E6.9C.A8"></span>木</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=13" title="節を編集: 木"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>根（root）という頂点を持ち、 </p> <div class="mw-heading mw-heading3"><h3 id="順序木"><span id=".E9.A0.86.E5.BA.8F.E6.9C.A8"></span>順序木</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=14" title="節を編集: 順序木"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading2"><h2 id="問題の解答"><span id=".E5.95.8F.E9.A1.8C.E3.81.AE.E8.A7.A3.E7.AD.94"></span>問題の解答</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=15" title="節を編集: 問題の解答"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>　問題の解答を記載しておく。 </p> <div class="mw-heading mw-heading3"><h3 id="問題1_2"><span id=".E5.95.8F.E9.A1.8C1_2"></span>問題1</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=16" title="節を編集: 問題1"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>(1)<br /> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{3}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{1},v_{5}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\},\{v_{2},v_{5}\},\{v_{3},v_{5}\}\})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <mo stretchy="false">(</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo>,</mo> <mo fence="false" stretchy="false">{</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{3}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{1},v_{5}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\},\{v_{2},v_{5}\},\{v_{3},v_{5}\}\})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/77b05f3ec773955117dc5d5574389e664d805b33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:80.023ex; height:2.843ex;" alt="{\displaystyle G_{3}=(\{v_{1},v_{2},v_{3},v_{4},v_{5}\},\{\{v_{1},v_{3}\},\{v_{1},v_{5}\},\{v_{2},v_{3}\},\{v_{2},v_{4}\},\{v_{2},v_{5}\},\{v_{3},v_{5}\}\})}"></span><br /> (2) </p> <ul class="gallery mw-gallery-traditional"> <li class="gallerybox" style="width: 235px"> <div class="thumb" style="width: 230px; height: 150px;"><span typeof="mw:File"><a href="/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wikibooks_graph_theory5.png" class="mw-file-description" title="'"`UNIQ--postMath-00000021-QINU`"'"><img alt="'"`UNIQ--postMath-00000021-QINU`"'" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Wikibooks_graph_theory5.png/193px-Wikibooks_graph_theory5.png" decoding="async" width="193" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Wikibooks_graph_theory5.png/289px-Wikibooks_graph_theory5.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Wikibooks_graph_theory5.png/386px-Wikibooks_graph_theory5.png 2x" data-file-width="448" data-file-height="279" /></a></span></div> <div class="gallerytext"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{4}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>G</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle G_{4}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/149de5cbc9bd78a60484b9c011a9020531255118" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{4}}"></span></div> </li> </ul> <div class="mw-heading mw-heading2"><h2 id="ファイルのダウンロード"><span id=".E3.83.95.E3.82.A1.E3.82.A4.E3.83.AB.E3.81.AE.E3.83.80.E3.82.A6.E3.83.B3.E3.83.AD.E3.83.BC.E3.83.89"></span>ファイルのダウンロード</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&action=edit&section=17" title="節を編集: ファイルのダウンロード"><span>編集</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>以下のURLにアクセスするとファイルをダウンロードすることができる。もちろん、自由に利用して構わない。<br /> <a rel="nofollow" class="external free" href="https://skydrive.live.com/redir.aspx?cid=322baa2fe886dd76&resid=322BAA2FE886DD76!230&parid=root">https://skydrive.live.com/redir.aspx?cid=322baa2fe886dd76&resid=322BAA2FE886DD76!230&parid=root</a> (リンク切れ)<br /> この教科書に利用されているファイルWikibooks graph theory*.pngはgraph*.svgやgraph*.png,graph*.epsの3種類の形式で保存されている。そのため、様々な用途に利用できる。フォルダとして一括でダウンロードすることも可能である。 </p>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">"<a dir="ltr" href="https://ja.wikibooks.org/w/index.php?title=グラフ理論&oldid=248294">https://ja.wikibooks.org/w/index.php?title=グラフ理論&oldid=248294</a>" より作成</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/%E7%89%B9%E5%88%A5:%E3%82%AB%E3%83%86%E3%82%B4%E3%83%AA" title="特別:カテゴリ">カテゴリ</a>: <ul><li><a href="/wiki/%E3%82%AB%E3%83%86%E3%82%B4%E3%83%AA:%E6%95%B0%E5%AD%A6" title="カテゴリ:数学">数学</a></li><li><a href="/wiki/%E3%82%AB%E3%83%86%E3%82%B4%E3%83%AA:%E9%9B%A2%E6%95%A3%E3%82%B0%E3%83%A9%E3%83%95" title="カテゴリ:離散グラフ">離散グラフ</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> このページの最終更新日時は 2024年5月10日 (金) 09:48 です。</li> <li id="footer-info-copyright">テキストは<a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.ja">クリエイティブ・コモンズ表示-継承ライセンス</a>のもとで利用できます。追加の条件が適用される場合があります。詳細については<a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use">利用規約</a>を参照してください。</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/ja">プライバシー・ポリシー</a></li> <li id="footer-places-about"><a href="/wiki/Wikibooks:%E3%82%A6%E3%82%A3%E3%82%AD%E3%83%96%E3%83%83%E3%82%AF%E3%82%B9%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6">ウィキブックスについて</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikibooks:%E5%85%8D%E8%B2%AC%E4%BA%8B%E9%A0%85">免責事項</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">行動規範</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">開発者</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/ja.wikibooks.org">統計</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookieに関する声明</a></li> <li id="footer-places-mobileview"><a href="//ja.m.wikibooks.org/w/index.php?title=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">モバイルビュー</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-6d94db5ff4-6q9gz","wgBackendResponseTime":199,"wgPageParseReport":{"limitreport":{"cputime":"0.059","walltime":"0.195","ppvisitednodes":{"value":298,"limit":1000000},"postexpandincludesize":{"value":265,"limit":2097152},"templateargumentsize":{"value":26,"limit":2097152},"expansiondepth":{"value":6,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":6726,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 15.185 1 -total","100.00% 15.185 1 テンプレート:Pathnav"," 23.14% 3.514 1 テンプレート:Pathnav/link"]},"cachereport":{"origin":"mw-web.codfw.main-697b7966c5-wfb4n","timestamp":"20241126193641","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"\u30b0\u30e9\u30d5\u7406\u8ad6","url":"https:\/\/ja.wikibooks.org\/wiki\/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96","sameAs":"http:\/\/www.wikidata.org\/entity\/Q131476","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q131476","author":{"@type":"Organization","name":"\u30a6\u30a3\u30ad\u30e1\u30c7\u30a3\u30a2\u30d7\u30ed\u30b8\u30a7\u30af\u30c8\u3078\u306e\u8ca2\u732e\u8005"},"publisher":{"@type":"Organization","name":"\u30a6\u30a3\u30ad\u30e1\u30c7\u30a3\u30a2\u8ca1\u56e3","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2012-02-10T12:02:49Z","dateModified":"2024-05-10T09:48:20Z","headline":"\u30b0\u30e9\u30d5\u306b\u95a2\u3059\u308b\u6570\u5b66\u7406\u8ad6"}</script> </body> </html>

CINXE.COM

グラフ理論 - Wikibooks