设有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是单向连通图,但不是强连通图,问:在 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中至少加几条边所得图 [tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex] 就能成为强连通图?

2022-06-03

设有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是单向连通图,但不是强连通图,问:在 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中至少加几条边所得图 [tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex] 就能成为强连通图?

答案：

     [tex=0.714x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是单向连通图，但不是强连通图，由定理 14.8 与定理 14.9 可知,[tex=0.714x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中存在经过每个顶点至 少一次的通路,但不存在经过每个顶点至少一次的回路.设 L 是 [tex=0.714x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中经过每个顶点至少一次的通 路,[tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 与[tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex]为始点与终点.在 [tex=0.714x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中加边 [tex=4.286x1.071]8ZGOkn3GIVVe8KM//JQ2ooUnxJY/HYywE54oGtM9WtU=[/tex] 得有向图 [tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex],则[tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex]中存在经过每个顶点至少一次 的回路.由定理 14.8 可知,[tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex] 是强连通图.所以,加 1 条边即可.

举一反三

内容

0
设简单图[tex=10.643x1.357]nxj1BqvkxphNtZmZgeH5FJ0YUz/NX0EZ5/xEOTaUs7aMuABGhGKiGf02taxfQzALXOiyMzHR2rZ+DKYrGODY/g==[/tex]，其中[tex=5.857x1.357]3I+hCoBURGNOyJYqwca15BuCqlhAlMN8cNu8jtGWfSA=[/tex][tex=11.714x1.357]afFzFAa9T4ubfmc/D1zVyyuZcDoigt4NyCEiVBG9GO30qRAlN4ZVP2et+g1EMH7Z[/tex][tex=14.0x1.357]naM7nTy9WvxXK54pAUdQzk5gKQHJMSatTdTrnWO/V6FwJE+9a+tlLcKuNT8U33aE[/tex][tex=11.643x1.357]a5oFJfXo0Q5MfUxgu9yw64KTwgvpBIaWIimO+TBLXLXYuXURvbxJFHpfvKldKQ4S[/tex][tex=16.5x1.357]zC6aiC+3J8aA3HzuMSYqT/pLcMjOBzYswvUIxe5OjlL29b8hF+jGIvmfrWpBdaHoMVIDvRrssKL+1/BARoF5Vg==[/tex][tex=16.357x1.357]SGDgWvwH6xUwLkj3dRR8aO0ACc/Tbw0pGI1U7fQr6xBWlW8bMFe8+h8ghw8yngIIqkQtMKvSlwlUpl7yO6/xsg==[/tex][tex=14.071x1.357]bLh9H82/iOSVQ+2PQtcn5MwYQUIE9Sz8rJQNA9Nol095uC5bKGA6wimQ+r7Bqu6/[/tex]画出各图，试问：（1）哪些图是有向图？哪些图是无向图？（2）哪些是强连通图？哪些是单向连通图？哪些是弱连通图？
1
有向图[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 如图 14.15 所示. [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex]长度为 1,2,3,4 的通回路各为几条?[img=249x227]17920709adc1a87.png[/img]
2
有向图[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 如图 14.15 所示. [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]z1WgSpi7t4Cme8y5zX37vg==[/tex] 长度为 1,2,3,4 的通路各为几条?[br][/br][img=249x227]17920709adc1a87.png[/img]
3
有向图[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 如图 14.7 所示，回答下列各题.[br][/br][img=294x218]17916c309166f11.png[/img][br][/br](1) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中有几个非同构的圈(初级回路)?(2)[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中最长的路径长度为几?(3) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中最长的简单通路长度为几?(4) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是哪类连通图?[br][/br](5) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中长度为 1,2,3,4 的通路在定义意义下各有多少条? 其中各有多少条回路?(6) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中长度小于等于 4 的通路在定义意义下有多少条? 其中各有多少条回路?
4
设[tex=4.643x1.357]6FXcyAQcSCJu/QJ0UPhDt3qVYCmBfbfb+jyTQRFiiLM=[/tex]为有向图,[tex=23.214x1.357]wCkem8yA1lKvF6bFMgXkXE9ou/eq7lsMjOVx/sEztW++INlj1VF0o4isPjmaPCUFyjfneIbtjYrfUTTe+qgwsV/Q1F6Vkb40KaHmM7w1AKsmAiaUiyJc3CxzhESRVfuh[/tex] 是未知类型：{'options': ['强连接图', '单向连接图', '弱连接图', '不连通图'], 'type': 102}