图论-王树禾-答案

图论第一次作业Bybyh|E(G)|,2|E(G)|2G1.1举出两个可以化成图论模型的实际问题略1.2证明其中是单图证明：（思路）根据单图无环无重边的特点，所以最大的情形为任意两个顶点间有一条边相连，即极端情况为。•1.4画出不同构的一切四顶单图•0条边：1条边：•2条边：3条边：•4条边：5条边：•6条边：1.10G≅𝐻当且仅当存在可逆映射𝜃:𝑉𝐺→𝑉𝐻，使得𝑢𝑣∈𝐸𝐺⇔𝜃𝑢𝜃𝑣∈𝐸𝐻，其中𝐺和𝐻是单图。（证明充分性和必要性）•必要性•若𝐺≅𝐻，由定义可得，存在可逆映射𝜃:𝑉𝐺→𝑉𝐻𝜑:𝐸𝐺→𝐸(𝐻)当且仅当𝜓𝐺𝑒=𝑢𝑣时，𝜓𝐻𝜑𝑒=𝜃𝑢𝜃(𝑣)，所以𝑢𝑣∈𝐸𝐺⇒𝜃𝑢𝜃𝑣∈𝐸𝐻•充分性•定义𝜙:𝐸𝐺→𝐸(𝐻)，使得𝑢𝑣∈𝐸𝐺和𝜃𝑢𝜃𝑣∈𝐸(𝐻)一一对应，于是𝜙可逆，且𝜓𝐺𝑒=𝑢𝑣的充要条件是𝜓𝐻𝜑𝑒=𝜃𝑢𝜃𝑣，得𝐺≅𝐻1.12求证(a)𝜖𝐾𝑚,𝑛=𝑚𝑛，(b)𝐺是完全二分图，则𝜖𝐺≤14𝑣𝐺2•(a)对于𝐾𝑚,𝑛，将顶集分为𝑋和𝑌，使得𝑋∪𝑌=𝑉𝐾𝑚,𝑛，𝑋∩𝑌=∅，𝑋=𝑚，𝑌=𝑛，对于𝑋中的每一顶点，都和𝑌中所有顶点相连，所以𝜖𝐾𝑚,𝑛=𝑚𝑛•(b)设𝐺的顶划分为𝑋,𝑌，𝑋=𝑚,𝑌=𝑣−𝑚，则𝜖𝐺≤•𝜖𝐾𝑚,𝑣-𝑚=𝑣−𝑚𝑚≤𝑣24•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,1•(b)将顶点v分成两部分v’和v’’•v’={v|v=vi,1≤i≤k},•v’’={v|v=vi,ki≤n}•以v’点为顶的原图的导出子图度数之和小于•然后考虑剩下的点贡献给这k个点的度数之和最大可能为•1.37：证明无环图𝐺含二分生成子图𝐻，使得𝑑𝐻𝑣≥12𝑑𝐺𝑣对每个𝑣∈𝑉(𝐺)成立。•证明：•任取X,Y满足XUY=V(G)，X∩Y=ø，且令X,Y中的顶两两不相邻，所得的图是H且是二分子图，令H是G边数最多的二分生成子图，若存在vϵV(G)，使得dH(v)dG(v)，不妨设vϵX，则将v所连的边取消，换成dG(v)-dH(v)条边，且将v加入Y中，于是H的边数增加了dG(v)-2dH(v)条，与H边数最多矛盾，故原命题成立。21