离散数学2

集合论

第五章集合

5.1 集合与元素

#在python中生成n个元素集合(构建集合)
import random
import numpy as np
def createset(m,n):
    A=random.sample(range(m), n)
    A=set(A)
    return A
def main( ):
    m=200
    n=100
    A=createset(m,n)
    return A
main()

归纳定义法

1) 基本项

非空集 S0 $\subseteq$ A；

2) 归纳项

一组规则，从A中元素出发，依据这些规则所获得的元素仍然是A中的元素；

3) 极小化

保证 A中每个元素都可通过有限次使用 1) 或 2) 来获得。如果集合 S $\subseteq$ A 也满足 1)和 2)，则 A $\subseteq$ S 。（如果集合 S $\subseteq$ A 也满足 1)和 2)，则 S = A ）

极小化保证 A 是满足 1) 和 2) 的最小集合。

5.2 集合间的相等和包含关系

集合相等

集合的包含关系（真子集，子集）

空集是唯一的

5.3 幂集

幂集

集合 A 的全部子集构成的集合称为A的幂集, 记作$\rho(A)$。 ρ (A) = { X│X $\subseteq$A }

$B\subseteq C \Leftrightarrow B\in \rho(C)$

基数

有穷集合A中所含有元素的个数称为A的基数。记作#A

幂集特征

5.4 集合的运算

集合运算：∩、∪、~（补，也称绝对补）、$-$（差，也称相对补）、$\oplus$（对称差）
n个集合的∩和∪，集合的聚合上的∩和∪。

集合族或集合的聚合

如果一个集合的所有元素都是集合，则称该集合为集合族或集合的聚合。

等值式模式

集合恒等式

5.4.2

对集合恒等式的说明

其他常用性质

$A-B=A\cap \sim B$
设 A 和 B是全集U的子集，$B=\sim A$当且仅当 A $\cup$ B = U 和 A $\cap$ B = $\varnothing$
设 A 和 B是全集U的子集，则下列命题等价：

（1）A $\subseteq$ B

（2）A $\cup$ B = B

（3）A $\cap$ B = A

（4）A $-$ B = $\varnothing$

注：该定理常用于证明两个集合的包含关系。

证明（I）两个集合相等常用以下两种方法：
1）集合相等定义 (元素分析法）
2）集合恒等式（等式推理）

5.5 有穷集的计数原理

5.5.2

5.6 集合的归纳定义法

定义程式

字符串

字符串相等与连接

字符串前缀，后缀，子串，$\sum *$，$\sum +$

5.6.4

5.6.5

语言，语言的运算，关系性质

5.6.6

5.6.7

5.6.8

5.6.9

5.7 有序偶和笛卡儿乘积

有序偶

定义

任给两个对象 x 和 y，将它们按规定的顺序构成的序列，称之为有序偶，记为〈 x，y 〉。

x 称为有序偶的第一元，y 称为第二元。

有序偶的集合表示

〈 x，y 〉= { { x }，{ x，y } }

n元序偶

笛卡儿乘积

定义

A×B = {〈x，y〉| x$\in$A $\wedge$ y $\in$ B }

性质

(1) 不满足交换律
(2) 不满足结合律
(3) 当A = $\varnothing$ 或 B = $\varnothing$ 时，A×B = $\varnothing$
(4) # (A×B) = #A · #B (A，B 为任意有限集)

5.7.2

5.7.3

5.7.4

第六章关系

6.1 关系及其性质

一、关系的定义

二、关系的表示

关系矩阵

关系图

三、关系的性质(自反、反自反、对称、反对称、传递)

6.1.7

6.1.8

关系图和关系矩阵中五种性质的表述

思考题：设 A 为恰有 n 个元素的有限集A

可以以3个元素的集合=={1,2,3}==举例

6.2 关系的运算

关系的交并差补集

复合关系

复合关系的结合律

设R，S，P分别是X 到 Y、 Y 到 Z、 Z 到 W的关系，则 ( R · S ) · P ＝ R · ( S · P ) 。

关系的幂运算

用矩阵运算来表示两个关系的复合

关系复合的性质

关系的逆

将关系R中每个有序偶的第一元和第二元对换所得到的关系, 称为R的逆关系，记作$R^{-1}$，

关系的一个逆运算定理

思考题

二元关系性质的判断条件

利用矩阵思考更方便

闭包

记忆：$r->reverse,s->symmetric,t->transmit$

用闭包来判断是否自反、对称、传递

1）R是自反的当且仅当 r(R) ＝ R；

2）R是对称的当且仅当 s(R) ＝ R；

3）R是传递的当且仅当 t(R) ＝ R 。

定理 6.3 设 R 是集合A上的关系，则 $r (R) ＝ R∪I_A$。

定理 6.4 设 R 是集合 A 上的关系，则 $s (R) ＝ R∪R^{-1}$ 。

定理 6.5 设 R 是集合A上的关系，则 $t(R) = R∪R^2∪R^3∪…∪R^n$

闭包的性质(注意rs/sr/rt/tr/st/ts)

巧记结论：有自反的交换顺序后仍然相等

计算顺序：比如$st(R)$，先算$s(R)$，再算$t(R)$。

$R^*=自反传递闭包=rt(R)$

$R^+=传递闭包=t(R)$

6.3 次序关系

偏序（半序）关系

全序关系（也称线序）

可比的

对于偏序集合〈P , ≤〉，x , y ∈P，如果有 x≤y 或者 y≤x，就说P的元素 x 和 y 是可比的。

例：〈N , ≤〉,〈N , ≥ 〉都是全序结构。它们中的任意元素 x 和 y 都是可比的，而〈 P(A) , $\subseteq$ 〉,〈 $I^+$ , | 〉都不是全序结构

严格偏序关系，又称拟序关系

反自反、传递==>反对称

遮盖

哈斯图

偏序结构通常用简化的关系图来表示，这种关系图称为偏序结构图或哈斯图。

偏序结构中的特殊元素（最大元，最小元，极大元，极小元，最大上界，最小下界）

极大元，极小元——仅仅是不存在比这些更大（小）的元素，可以是因为关系并不是全序产生的

最大元，最小元，最大上界，最小下界——每个元素（上下界）都要比这个元素（上下界）小（大），条件更强

6.3.7

良序结构

一个偏序结构〈P , ≤〉，如果 P的每一个非空子集都有一个最小元，则称≤为良序关系，〈P , ≤〉为良序结构。
每个良序结构都是全序结构（因为对于任意非空子集都有最小元）
但并非每个全序结构都是良序的，当然有穷的全序结构一定是良序的。
- 例子：〈N , ≤〉是全序结构，也是良序结构；〈I , ≤〉是全序结构，但不是良序结构。

良序的充要条件

定理A 若≤为集合P上的偏序关系，则 ≤ 为P上良序关系，当且仅当 1）≤为P上的全序关系； 2）P 的每个非空子集都有最小元。

定理B 设〈A, ≤〉为全序结构，则〈A, ≤〉是良序结构的充要条件是：不存在 A 中元素的无穷序列 a0 , a1 , a2 , … ,使得对每个 i$\in$N，皆有 $a_{i+1}<a_i$——简单地说就是不存在 A 中元素的无穷递降序列。

6.4 等价关系与划分

等价关系

集合A上的关系R是自反，对称，传递的，则称R为A上的等价关系。

对于任意正整数 m，模m同余关系是等价关系。

等价类

设 R 是集合A上的等价关系。对于每个x∈A，A中与 x 有关系 R 的元素的集合 称为 x关于R的等价类，简称为 x 的等价类，记作 [ x ] $_R$，

[ x ] $_R$ ＝｛ y｜y∈A ∧ x R y ｝

等价类相关定理

(1) 对于每个 x∈A，x∈[x] $_R$ ，即 [x]$_R$ 是A的非空子集。

(2) [x]$_R$＝[y]$_R$当且仅当 x R y 。

(3) 若 x, y∈A 且 x$\overline R$y，则 [x]$_R$$\cap$ [y]$_R$ = $\varnothing$ 。

(4) $\bigcup_{x \in A} [x]_R$＝ A, 其中 [x]$_R$ 表示所有等价类的并集。

商集（全体元素等价类集合组成的集合）

定义设 R是集合A上的等价关系，所有等价类组成的集合称为 A 关于 R 的商集，记作 A / R，即: A / R ＝｛ [x]$_R$｜ x ∈A ｝

划分

设 A 是非空集合, π$\subseteq$ρ(A) (即π包含 A 的若干子集)。若π满足以下三个条件，则称π为 A上的一个划分: (1) 对于每个 S∈π，S ≠ $\varnothing$； (2) 对于任意 B, C ∈π，若 B≠C，则 B $\cap$ C＝$\varnothing$；（若 B $\cap$ C ≠$\varnothing$，则B ＝ C） (3) $\cup \pi$ ＝ A 。

把π中的元素称为划分块，π中划分块的个数称为秩, 有有穷个划分块的划分称为有穷划分, 否则称为无穷划分.

等价关系，划分，商集，等价类的关系

非空集合 A 上的等价关系 R, 决定了A上的一个划分，这个划分就是商集 A / R 。

由π确定的等价关系

定理设π是非空集合 A 上的一个划分，若令：R${\pi}$ ＝ {〈x, y〉| 存在 S∈π使得 x, y ∈ S ｝即: x R${\pi}$ y 当且仅当 x 和 y 在π的同一个划分块中，则 R${\pi}$ 必是 A 上的等价关系且 A／R${\pi}$ = π。称 R$_{\pi}$ 为由π确定的等价关系。

上述定理表明，由等价关系能够产生一个划分。同样，由一个划分也可以产生一个等价关系。

例: U$_X$, I$_X$ 分别是 X 上的全域关系和恒等关系，则 X / U$_X$ = { X }， X / I$_X$ = { {x} | x$\in$X }

I/$_{=m}$—代表模m同余的等价关系

第七章函数

==一般考试中函数指全函数==

7.1 基本概念

函数的定义和判定

函数是特殊类型的==二元关系==，关系允许，但函数==不允许一对多==。关系和函数都允许多对一。

函数概念本质是约束二义性，主要限制的是关系概念中一对多。

定义域值域

定义域——$Domain \ of \ definition$

值域——$Range$

部分函数

如果从集合 X 到 Y 的二元关系是单值的

即 f 满足以下条件：若〈x，y1〉∈f 且〈x，y2〉∈f，则 y1 = y2 。就称 f 为从==X 到 Y 的部分函数(partial function)==。若 f 是部分函数且〈x , y〉∈f，则称 y 是 f 在 x处的值（在 f 作用下x的像点)，记为 y = f (x)，并称 x 为 y 的一个源像点。

部分函数——部分有定义的函数——即 $dom(f)\subseteq X$

设 f 为从集合 X 到集合 Y 的 部分函数.

若$dom(f)= X$，则称f为从X到Y的一个全函数。记为：$f:X\rightarrow Y$
若$dom(f)\subset X$，则称f为从X到Y的一个严格部分函数。
若$ran(f)=Y$，则称f为从X到Y==上==的一个部分函数。
若$ran(f)\subset Y$，则称f为从X到Y==内==的一个部分函数。
若对任意的 x1，x2∈dom (f ) ，当 x1 ≠ x2 时, 皆有 f ( x1 ) ≠ f ( x2 )，即: 当 f ( x1 ) = f ( x2 ) 时, 皆有 x1 = x2 ,当 ƒ 为 X 到 Y 的全函数时, f 既满足单值性，且处处有定义

函数的限制(即限制定义域)

设函数ƒ : X→Y，A $\subseteq$ X，则ƒ∩ (A×Y) 是从 A 到 Y 的函数，称为 ƒ 在 A上的限制，记作 ƒ│$_A$ , 又称 ƒ 为 ƒ│$_A$到 X 的延拓。 ƒ│$_A$可表示为：ƒ│$_A$ ＝｛〈x , y〉│〈x , y〉∈ƒ ∧ x∈A｝

部分函数的像和源像

设 f 为从集合 X 到集合 Y 的部分函数，A $\subseteq$X 且 B$\subseteq$ Y。

令f [A] = { y｜有 x ∈A 使 y = f (x) }
f$^{-1}$[ B ] = { x ∈X｜有 y ∈B 使 y = f (x) }

称 f [ A ] 为 A 在 f 下的像，f $^{-1}$ [ B ] 为 B 在 f 下的源像。

即： f [A] = { f (x)｜x ∈A 且 f (x)↓ } f $^{-1}$ [ B ] = { x ∈X ｜ f (x)↓ 且 f (x) $\subseteq$ B }

dom (f ) = { x ∈X｜有 y ∈Y 使 y = f (x) } = f $^{-1}$[Y]
ran (f ) = { y ｜有 x ∈X 使 y = f (x) } = f [X]

小结：从集合 X 到 Y 的二元关系 f 几个重要知识点

定理

设 f 为从集合 X 到集合 Y 的部分函数

设 f 为从集合X到Y的部分函数, Ａ $\subseteq$ ρ (X), В $\subseteq$ ρ (Y)

定理若 f 为从集合 X 到 Y 的部分函数且 A $\subseteq$ X ，则

X到Y的全函数集合

$Y^X=$ {$f|f:X \rightarrow Y$} 从X到Y的函数个数？ $Y^X$个即：#$Y$^(#$X$)个

两道例题

719

7.2 函数的复合

复合关系与对应函数

函数复合的约定写法

$h(x)=f(g(x))$

关系：内层的函数符号$g$在左

函数：内层的函数符号$g$在右

函数复合的定义

复合函数的定义域与值域

函数复合运算的性质

恒等函数

集合 X上的恒等关系 $I_X$ = {〈x, x〉| x∈X } 为 X 到 X 的恒等函数。

结合律

函数的幂运算

7.3 特殊性质的函数和逆函数

满射、单射、双射

全函数：$f:X\rightarrow Y $

满射：$ran(f)=Y$

单射：$\forall x_1 \in X ,\forall x_2 \in X (x_1\neq x_2\rightarrow f(x_1)\neq f(x_2))$

双射：单满射

常值函数：$\forall x\in X,\exists c \in Y,f(x)=c$

函数与复合函数之间的性质关系定理

$f:X\rightarrow Y ,g:X\rightarrow Y$

(1) $若f、g是满射,g\circ f也是满射$

(2) $若f、g是单射,g\circ f也是单射$

(3) $若f、g是双射,g\circ f也是双射$

规则：左满右单

(1) $若g\circ f是满射,则g是满射$

(2) $若g\circ f是单射,则f是单射$

(3) $若g\circ f双射,则g是满射且f是单射$

左逆、右逆、逆（逆<=>一个函数同时为左逆和右逆）

定义

唯一逆

4个可逆的等价条件

7.1.12

复合函数的逆

7.1.13

7.4 集合的特征函数

定义

特征函数的性质

用特征函数证明集合恒等式

第八章自然数和基数

8.1 自然数及数学归纳法

主要概念：集合的后继
主要方法：归纳原理、第一归纳法、第二归纳法

自然数引进方法

公理化方法：皮亚诺公理
构造性方法：借助集合论，具体构造出N

自然数构造的出发点

1) 自然数的==各种性质==( 运算、大小次序及基本定律 ) ,都可以从 Peano 公理一一推导出来；

2) 证明构造出来的 “自然数” ==满足Peano公理==，因此具有普通自然数的一切性质。

后继集合

后继集合定义：$A^+=A \cup {A}$
每个集合都有唯一的一个后继。

引理

构造自然数系统

法1：冯诺依曼（Von Neumann）方案

法2：自然数集合 N——归纳定义法

“小于” 关系

定义“+”和“×”

815

引理2

816

Peano公理

作为集合的自然数的性质

数学归纳法

8112

8114 8113

8.2 基数

本节讨论度量和比较两个集合大小的方法。

1.等势

设 A 和 B 为二集合，若存在从 A 到 B 的双射，则称 A 和 B 对等，或称 A 和 B 等势，记为 A ～ B。

等势关系的性质

对于任何集合 A , B , C ，均有：
(1) A ~ A；
(2) 若 A ~ B , 则 B ~ A；
(3) 若 A ~ B , B ~ C , 则 A ~ C。

即等势关系有自反性 , 对称性和传递性，因此等势是集合族上的等价关系。

集合有穷（可数）的定义

集合是有穷（可数）的，当且仅当它与某个自然数集合等势，否则就是无穷的。

2.无限集

无穷集合可以与它本身的真子集等势

任何无限集都如此，这正是无限集与有限集之间的本质区别，也可以把它作为无限集的定义。

鸽笼原理（抽屉原理）

任何有限集都不能与它的真子集对等 =>导出有穷集合与无穷集合的根本差别：=>任何与自身真子集等势的集合均是无穷集合。

这个定理也叫抽屉原理，可通俗表述为：“如果把 n+1 本书放进 n 个抽屉里，至少在一个抽屉里有两本或两本以上的书。”

定理8.1 任意有穷集合 A 唯一地与一个自然数等势。

定义8.7 ( 有穷集合的基数 )

对于任意有穷集合 A , 存在唯一的自然数 n , 使得 A ~ n, 称 n 为 A 的基数 , 记为 #A （ card (A) 或｜A｜）

对于无限集的基数，我们规定特殊的记号，例如令#( N ) = $\aleph_0$ 是希伯来语的第一个字母，念作阿列夫。

3.集合的基数

基数相等和大小顺序

定义：设 A 和 B 为二集合。

1) 如果 A～B，就称 A 和 B 的基数相等，记为 # (A) = # (B)。
2) 如果存在从 A 到 B 的单射，
就称 A 的基数小于等于 B 的基数，记为 #(A) $\leq$ #(B)，
或称 B 的基数大于等于 A 的基数，记为 #(B) $\ge$ #(A) 。
3) 如果 #(A) $\leq$ #(B) 且 #(A) ≠ #(B)，
就称 A 的基数小于 B 的基数，记为 #(A) < #(B)，
或称 B 的基数大于 A 的基数，记为 #(B) > #(A)。

任何两个基数都可以比较大小

设 A 和 B 为任意两个集合，则#(A) $\leq$ #(B) ，或 #(B) $\leq$ #(A) ，二者之中至少有一个成立。

基数的相等关系 “ = ” 是等价关系

设 A、B 和 C为三集合，则有
1） #(A) = #(A)； 2）若 #(A) = #(B)，则 #(B) = #(A)； 3）若 #(A) = #(B) 且 #(B) = #(C)，则 #(A) = #(C)

基数的小于等于关系“ $\leq$ ”是半序关系

设 A，B 和 C 为三集合，则有

1) #(A) $\leq$ #(A)；
2) 若 #(A) $\leq$ #(B) 且 #(B) $\leq$ #(A)，则#(A) = #(B)；
3) 若 #(A) $\leq$ #(B) 且 #(B) $\leq$ #(C)，则#(A) $\leq$ #(C)。
其中， 2）为著名的 Bernstein 定理。

定义8.8 ( 基数 )

设 F 是集合族 , ~ 是 F 上的等势关系。关系 ~ 在 F 上的等价类称为基数。对于 A $\in$ F , A 所属的等价类用 #A 表示 , 称之为 A 的基数。对于 A , B $\in$ F ： #A = #B $<=>$ A ~ B 。

定义8.9（可数无穷集合）

任何与自然数集合等势的集合称为可数无穷集合。可数无穷集合的基数，用 $\aleph_0$ 表示，读作阿列夫零。

定义8.10（可数、不可数集合）

如果一个集合是有穷集合或是可数无穷集合 , 就称它为可数集合；如果一个集合是无穷的，而且不是可数的，就称它为不可数集合。

无穷集的等价条件

定理：以下三个条件等价：

1) A 为无穷集；
2) A 有可数无穷子集；
3) A 有与它对等的真子集。

定理8.2：任何无穷集合必含有可数无穷子集。

定理8.3：可数无穷集合的无穷子集必是可数无穷的。

可数无穷集合的并集和可数无穷集合的笛卡儿乘积都仍然是可数无穷集合 =>可以证明：偶数集E ~ N , N$\times$N ~ N , Q~N , Z ~ N
可见：偶数集合、平面上整格点的集合、有理数集合、整数集合都是可数无穷集合。

定理：实数集合 R 是不可数的。

基数的个数也是无限的，且无最大者

定理8.4：实数集合 R 是不可数的

与集合 R 等势的集合的基数 , 用 $\aleph$来表示 , 并称为连续统的势 . #$\rho$ (N) 记为 $\aleph$

定义 8.14：若#A = $\alpha$ , #B = $\beta$, 且 A $<$ B , 则称 $\alpha$ 小于 $\beta$ , 记为 $\alpha$ < $\beta$ .

因为自然数集合是实数集合的真子集 , 由定理 8.4的证明可知 , 有 N $<$ R 和 $\aleph_0$ < C ;又因为任何无穷集合都包含一个可数无穷子集 , 故 $\aleph_0$ 是最小的无穷基数 . 即对于任何无穷集合 A , 有 N$\leq$A ; 对任何无穷基数 k , 有$\aleph_0\leq$k .

定理 8.5 对于任意集合 A , A $<\rho$ (A) , $\rho$ (A)是 A 的幂集.

4.常用结论

$#(N)=#(N^{+})=#(Q)=\aleph_0$

$#(R)=#(\rho(N))=\aleph$

图论

第九章

第九章其他资料

Python工具库：networkx

官网：https://networkx.org/

教程：https://blog.csdn.net/qq_32284189/article/details/80134768

9.1图论的基本概念 9.2 图的基本结构

无向图、有向图

$\Psi:E\rightarrow V \times V:边集到点集的笛卡尔积映射$

注：V是点集，E是边的集合

自圈、平行边、简单图、多重图

图的最本质内容：结点和边的对应关系。=> 用几何图形表示图，小圆圈表示结点

关联、邻接 —— 结点和边的关系

关联：边与点相连的关系

临接：边与边，或点与点相连的关系

度

奇结点、偶结点、孤立点、端点

度为奇数的结点称为奇结点；
度为偶数的结点称为偶结点。
度为 0 的结点称为孤立点；
度为 1 的结点称为端点。

零图、平凡图、d度正则图、完全图

同构

两个图同构的必要条件

以上三条同时成立则是充分条件

9.2子图和图的运算

子图、真子图、生成子图

生成子图：点集与母图一样

其他两个：点集包含于母图点集

由结点集导出的子图 ($G[V’],G-V’=G[V-V’]$)

由边集导出的子图

子图的几个特点

可运算、不相交

不相交或者边不相交仍然是可运算的

交、并、环和

注意：环合和并仅只有边集不同，点集和$\Psi$运算都为两个图的并集

定理：图的唯一性

运算 G – E’

运算 G + E’$_{\psi’}$（其实就是并运算）

补图

自补图：与其补图同构的简单无向图

图同构的必要条件

9.3路径、回路和连通性

路径

定义（路径，路径长度，开、闭路径，简单路径，基本路径）

简单路径——边无重复

基本路径——点无重复

开路径——起点$\neq$终点

闭路径——起点$=$终点

路径的另一组术语

链（chain or walk）：顶点和边交错出现的序列称为链，在序列中边的前后两个顶点正好是边的端点，序列的==第一个顶点==和==最后一个顶点==为链的==端点==，其余的点为==内点==。
迹（trail）：边互不相同的链称为迹。即迹中无重边。——迹是简单路径
路（path）：内部点互不相同的链称为路。即路中无重点。——路是基本路径

路径的基本性质

两个路径的基本定理（7.3.1,7.3.2）

证明7.3.1

证明7.3.2

（因为基本路径中的结点互不相同，即最多仅含 n个结点，所以所经过的边数必定小于 n。）

可达（注意R(v)——从v可以到达的全体结点的集合）

距离（测地线，距离，图的直径）

加权图（加权长度，最短路径，加权距离）

迪杰斯特拉（Dijkstra）算法

Dijkstra的python实现（个人向）

#n-->有n个点 m-->有m条有向边
#s-->起点 t-->终点
#a-->边的起点 b-->边的终点 c-->边的权值
n,m,s,t=map(int,input().split()) 
cos=[[float('inf') for j in range(0,n+1)] for i in range(0,n+1)]
for i in range(0,n+1):
    cos[i][i]=0
parent=[s for i in range(0,n+1)]
ap=[0 for i in range(0,n+1)]
dis=[float('inf') for j in range(0,n+1)]
dis[s]=0
for i in range(m):
    a,b,c=map(int,input().split())
    cos[a][b]=c
    if(a==s and c<dis[b]):
        dis[b]=c
ap[s]=1
while(1):
    mind=float('inf')
    mini=-1
    for i in range(1,n+1):
        if dis[i]<mind and ap[i]==0:
            mini=i
            mind=dis[i]
    ap[mini]=1
    if(mini==-1):
        break
    for i in range(1,n+1):
        if(ap[i]==0 and dis[i]>dis[mini]+cos[mini][i]):
            parent[i]=mini
            dis[i]=dis[mini]+cos[mini][i]
path=[]
e=t
while(e!=s):
    path.append(e)
    e=parent[e]
path.append(s)
for x in reversed(path):
    print(x,end=" ")
print()
print(dis[t])