设有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是单向连通图,但不是强连通图,问:在 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]中至少加几条边所得图 [tex=1.143x1.143]GavJ7my+24CfS9kgKVIUow==[/tex] 就能成为强连通图?
举一反三
- 给出3个4阶有向简单图[tex=4.429x1.214]V6077VMIvXVzIoKM5mjz4w==[/tex]，使得[tex=1.214x1.214]iyaS3IuvW2nHtD0XM06NDQ==[/tex]为强连通图；[tex=1.214x1.214]OrxFyiyr3zNn4yPPK+isSQ==[/tex]为单向连通图但不是强连通图；[tex=1.214x1.214]5gZPQcO8gZGT43dj+gbvNw==[/tex]是弱连通图但不是单向连通图，当然更不是强连通图。
- 试寻找3个4阶有向简单图[tex=4.429x1.214]uT/23VVcefrI0SKqk4S+SRFne3NkiaHFuN+VpDpQbfU=[/tex]，使得[tex=1.214x1.214]Ho8mAPpdke4daIdB3oO8tA==[/tex]为强连通图；[tex=1.214x1.214]w3UCvqjM/wRFMriPRfdAww==[/tex]为单向连通图，但不是强连通图；而[tex=1.214x1.214]LwBUvz7W/5ZmVPC1C2U8iw==[/tex]是弱连通图，但不是单向连通图，更不是强连通图。
- 有向图 [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 如图 14.23 所示.(1) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中 [tex=0.857x1.0]z1WgSpi7t4Cme8y5zX37vg==[/tex] 到 [tex=0.857x1.0]ZDCVElMiWIdShZcg4z/PtQ==[/tex] 长度为 1,2,3,4的通路各为几条?(2) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 到 [tex=0.857x1.0]H4Kf9rHTBSFrzdtxc2YGZA==[/tex] 长度为 1,2,3,4 的回路各为几条?(3) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 中长度为 4 的通路共有多少条?其中有多少条是回路?(4) [tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex] 是哪类连通图?
- 设有有向图[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]如图6.7所示，试求：（1）每个结点的引入次数与引出次数；（2）它的邻接矩阵[tex=1.571x1.214]rzf0jr3YGqLmoRnJWdiEDA==[/tex]；（3）[tex=0.857x1.0]PvQ1rNj9zmhWbdNmDhnQhA==[/tex]是强连通、弱连通还是单向连通？（4）求从[tex=0.571x0.786]HXNXn3AXpwdIpZt8+6oCEw==[/tex]到[tex=0.5x0.786]hycNLgozeED/VkKdun7zdA==[/tex]长度小于或等于3的通路数目.[img=337x313]1785f7fbc4ea378.png[/img]
- 设简单图[tex=11.571x1.357]R8KUwBI41NxOt56m8ehSJ/utbh0yylYBohywwJEDVTk29qLNSpcrxebNTuO8S5XLGosnZ/qnygmXU379ffX50Q==[/tex]其中 [tex=6.857x1.357]3I+hCoBURGNOyJYqwca15EODrdG0RtkvvZWkrhngePw=[/tex][tex=18.357x5.643]afFzFAa9T4ubfmc/D1zVyyuZcDoigt4NyCEiVBG9GO2QqIH5yzXR09VVMpjHK3/P0KAJmubQYPFI4VGrMDLoQPWmupAmKdXWrDnn+rdsLO6/ieCSqWntP1EKbG7iLLN41PUwTMEtMwxmARAxBFhpFDuOBANaXyPjSrr/P/AfGlmJvuOafyzrFbT3NZUDEyXXwkWvBwxiYvk+j79e9EWcTugDlFyN0borzOC+9/r25zGpDy7ShsNicvgmuyuWcFOeQ8/PXdYyJd8aDJC2Ml6Xjw==[/tex][tex=18.643x2.786]YWAdN29KD1BCHxNPKQbX6n4ehEz+qyUhbHylbvpYThq5l+FKfNtbRE9OfaAzs5UuXqQq2rrfsBKY50E/9k3fMcbUC/QBExLPXTkLUu8thTjFq/qNPHMPi4sbXOWnx34ivQ32L8I3zXmoi//4E4IRjppaV4ja+9K/u2plIPpZpC4c+g2qXiFKPalbKK31Dj9M[/tex]做出各图,试问:(1）哪些图足有向图?哪些图是无问图?(2）哪些是强连通图?哪些是单向连通图哪些是弱连通图?