Graph theory: Every vertex belongs to some component of the graph -

-

i know intuitively, every vertex of undirected graph must belong component of graph, since @ least, every vertex of graph connected itself. how can proven formally?

consider operator ~ on vertices in (possibly infinite) graph g, v1 ~ v2 iff there path between v1 , v2 (and allowing v ~ v). ~ equivalence relation on vertices(g), since reflexive, symmetric , transitive (you should verify each of these properties).

by definition of component, each equivalence class in vertices(g)/~ associated 1 component of g, , contains vertices of associated component. equivalence classes form partition of sets on defined, each vertex of g in @ least 1 equivalence class, , hence in 1 component.


Comments

Post a Comment

Popular posts from this blog

c++ - Delete matches in OpenCV (Keypoints and descriptors) -

-
i want check scene image against 2 train images. that, detect features , compute descriptors of both training images. before detecting, computing , matching scene image, delete matches of train1 , train2. because these matches won't facilitate matching of scene image train1 , train2. so, match train1 train2 , vector of matches trainidx , queryidx. how can delete these matches in keypoints-vector , descriptor matrix of train1 , train2? best regards, dwi i have done below: std::vector<cv::keypoint> keypoints[2]; cv::mat descriptor[2]; std::vector< cv::dmatch > matches; /* write code generate keypoints, descriptors , matches here... keypoint[0] -> train image 1 keypoints keypoint[1] -> train image 2 keypoints descriptor[0] -> train image 1 descriptors descriptor[1] -> train image 2 descriptors matches -> matched between train image 1 , 2 */ // logic keep unmatched keypoints , corresponding descriptor
Read more

java - Could not locate OpenAL library -

-
i writing game using slick2d library, uses lwjgl. lwjgl version 2.9.3. using netbeans 8. i tried adding sounds game, example music track on main menu. problem is, exception when run game, despite game still compiling , running except sound of course: sat mar 21 01:23:57 edt 2015 error:could not locate openal library. org.lwjgl.lwjglexception: not locate openal library. @ org.lwjgl.openal.al.create(al.java:156) @ org.lwjgl.openal.al.create(al.java:156) @ org.lwjgl.openal.al.create(al.java:102) @ org.lwjgl.openal.al.create(al.java:206) @ org.newdawn.slick.openal.soundstore$1.run(soundstore.java:295) @ java.security.accesscontroller.doprivileged(native method) @ org.newdawn.slick.openal.soundstore.init(soundstore.java:292) @ org.newdawn.slick.music.<init>(music.java:156) @ org.newdawn.slick.music.<init>(music.java:75) @ view.mainmenu.init(mainmenu.java:58) i didn't include rest of error states error happens in game code. the
Read more

sorting - opencl Bitonic sort with 64 bits keys -

-
i used nvidia sdk bitonic sort , works great me. 32 bits (uint) need ulong keys. have typically 2^14 keys @ time , power of 2. searched on not find kernel designed ulong. i tried modified nvidia sdk bitonic sort using ulong keys not work. kernel not crash after de call clenqueuendrangekernel got error : cl_invalid_command_queue can tell me how modify bitonic sort or radixsort, or can sort ulong keys? i running nvidia quadro 4000 opencl 1.1 cuda 6.5.20 full_profile used original nvidia sdk bitonicsort.cl i used"ulong" keys , value input , ouput instead of "uint" thanks helping i made work-around suit need. used 30 bits of key , 18 high bits of value sorting. changed comparators (2 lines): '#define mask 0xffffc000 // suit need from this: if( (*keya > *keyb) == dir ) this: if(((*keya > *keyb)||((*keya == *keyb)&&((*vala & mask)> (*valb & mask)))) == dir ) it works fine. but, still, it's work-a
Read more